Solution Set 10: Part A

Benjamin Bakker Mathematics 25a Prof. Berger

December 5, 2003

A.1. Find the rank of the matrix A = (a_{ij})_{1≤i,j≤n} in the following cases: (1) a_{ij} = i + j − 1.

Solution. The image of a matrix is spanned by its columns (actually the vectors whose coordinates are a column). The general strategy for these problems will be to use column operations to make as many columns as we can 0, and then show that the remaining columns are linearly independent so we know we can’t reduce it any further.

For n ≥ 2, the matrix is

(\begin{matrix}1 & 2 & ⋯ & n \\ 2 & 3 & & n + 1 \\ ⋮ & ⋮ & & ⋮ \\ n & n + 1 & ⋯ & n + n − 1 \end{matrix})

Multiplying the first by −1 and adding the second, we obtain (1 ⋮ 1) in the first column.

We can then subtract the sum of the second column and j − 2 times the first from the jth column to get all 0’s in the jth column. Thus, we have

(\begin{matrix}1 & 2 & 0 & ⋯ & 0 \\ 1 & 3 & 0 & & 0 \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ 1 & n + 1 & 0 & ⋯ & 0 \end{matrix})

The first two columns are clearly linearly independent, so the rank is 2. For n = 1, the rank is 1.

(2) a_{ij} = cos(α(i + j)) where α ∈ ℝ.

Solution. For n ≥ 2, the matrix is

cos 2α  cos 3α  ⋯ cos(n + 1)α
cos 3α  cos 4α  cos(n + 2)α
⋮
cos(n + 1)α cos(n + 2)α  cos 2nα

Note that cos(i + 2)α = cos(i + 1)α cos α − sin(i + 1)α sin α, so if C_{1} is the first column and C_{2} the second, as long as α is not a multiple of π,

(− sin α)(sin(i + 1)α)_{1≤i≤n} + (cos α)C_{1} = C_{2} ⇒ (sin(i + 1)α)_{1≤i≤n} = cot αC_{1} − csc αC_{2}

and therefore we may reduce to

cos 2α  sin 2α  cos 4α  ⋯ cos(n + 1)α
cos 3α  sin 3α  cos 5α  cos(n + 2)α
⋮  ⋮  ⋮  ⋮
cos(n + 1)α sin(n + 1)α cos(n + 3)α ⋯  cos 2nα

Let C′_{2} be the new second column. We can make the jth column by [cos(j − 1)α]C_{1} − [sin(j − 1)α]C′_{2}, and thus the image is spanned by the first two columns. For n ≥ 2, these two are clearly independent for α not a multiple of π, for if

0 = a (\begin{matrix}cos 2α \\ cos 3α \end{matrix}) + b (\begin{matrix}sin 2α \\ sin 3α \end{matrix})

for a, b not both zero, then

a cos 3α = a cos α cos 2α − a sin α sin 2α; b sin 3α = b sin α cos 2α + b cos α sin 2α

⇒ 0 = sin α(b cos 2α − a sin 2α) ⇒ (\begin{matrix}b & −a \\ a & b \end{matrix}) (\begin{matrix}cos 2α \\ sin 2α \end{matrix}) = (\begin{matrix}0 \\ 0 \end{matrix}) ⇒ (\begin{matrix}cos 2α \\ sin 2α \end{matrix}) = (\begin{matrix}0 \\ 0 \end{matrix})

since by assumption sin α ≠ 0 and the above matrix is invertible as long as a, b are not both zero. We thus have a contradiction, and the rank is 2. For α = nπ for some n ∈ ℤ, the matrix is

( 1 −1 1 ⋯; −1 1 −1 ; 1 −1 1 ; ⋮) or (1 1 1 ⋯; 1 1 1 ; 1 1 1 ; ⋮)

depending on whether n is odd or even, and the rank is clearly 1. If n = 1, then the rank is 0 if α is an odd half-multiple of π/2 (\frac{2n+1}{2} \frac{π}{2} ), and 1 otherwise.

(3) a_{ij} = (α + i + j)^{2} where α ∈ ℝ.

Solution. The matrix is

(\begin{matrix}(α + 2)^{2} & (α + 3)^{2} & ⋯ & (α + n + 1)^{2} \\ (α + 3)^{2} & (α + 4)^{2} & & (α + n + 1)^{2} \\ ⋮ & ⋮ & & ⋮ \\ (α + n + 1)^{2} & (α + n + 2)^{2} & ⋯ & (α + 2n)^{2} \end{matrix})

The jth column has ith entry (C_{j})_{i} = (α + i + j)^{2} = (α + i + j − 1)^{2} + 2(α + i + j − 1) + 1, and thus

C_{j} = C_{j−1} + 2 (1 ; 2 ; ⋮ ; n) + (2α + 2j − 1) (1 ⋮ 1)

and therefore we can build every column C_{j} from the three columns

C_{1} = ( (α + 2)^{2} ; (α + 3)^{2} ; ⋮ ; (α + n + 1)^{2}) , C′_{2} = (1 ; 2 ; ⋮ ; n) , C′_{3} = (1 ⋮ 1)

C′_{2}, C′_{3} are in the image; subtracting C_{2} from C_{3} and C_{1} from C_{2} we obtain

(\begin{matrix}(α + 2)^{2} & 2(α + 3) + 1 & 2(α + 4) + 1 & ⋯ & (α + n + 1)^{2} \\ (α + 3)^{2} & 2(α + 4) + 1 & 2(α + 5) & & (α + n + 1)^{2} \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ (α + n + 1)^{2} & 2(α + n + 1) & 2(α + n + 2) + 1 & ⋯ & (α + 2n)^{2} \end{matrix})

Subtracting the second from the third we then obtain C′_{3}, and we can then use that to make the second column C′_{2}.

Moreover, these three are linearly independent for n ≥ 3. If aC_{1} + bC′_{2} + cC′_{3} = 0, then all n rows of aC_{1} + bC′_{2} are equal. Thus, a(α + 2)^{2} + b = a(α + 3)^{2} + 2b = a(α + 4)^{2} + 3b; the first two give 2aα + 5a + b = 0, and the second and third give 2aα + 7a + b = 0, so a = 0 and then b = c = 0.

For n = 2, the first two are linearly independent, so the rank is 2 by a similar argument, and for n = 1 the rank is 1 if α ≠ −2, and 0 otherwise.

A.2. Let E be a vector space over a field K, and let F be a subspace (not equal to E). Prove that Vect(E \ F) = E (i.e. that every vector in E is a linear combination of vectors in E \ F). Make sure your proof works for every field K.

Solution. F ≠ E, so there is some nonzero x ∈ E \ F. For any v ∈ F, v − x is in E \ F, for if v − x ∈ F then since v ∈ F we would have v − (v − x) = x ∈ F. We then have v = (v − x) + x.

A.3. Let K be an infinite field, let V be a K-vector space of dimension n and let W_{1}, …, W_{k} be subspaces of V of dimension ≤ n − 1. Prove that V ≠ ∪_{i=1}^{k}W_{i}.

Solution. We will first show that for any n-dimensional K-vector space V, n ≥ 2, there are infinitely many different n − 1 dimensional subspaces. Take v_{1}, …, v_{n} to be a basis of V, and let W_{λ} = Vect(v_{1} + λv_{n}, v_{2}, …, v_{n−1}) for λ ∈ K. Each W_{λ} has dimension n − 1, and if W_{λ} = W_{λ′}, then for some a_{i} ∈ K

v_{1} + λ′v_{n} = a_{1}(v_{1} + λv_{n}) + a_{2}v_{2} + ⋯ + a_{n−1}v_{n−1}
⇒ 0 = (a_{1} − 1)v_{1} + a_{2}v_{2} + ⋯ + a_{n−1}v_{n−1} + (a_{1}λ − λ′)

and since (v_{i})_{1≤i≤n} is a basis, we must have a_{1} = 1 and thus λ = λ′ ⇒ W_{λ} = W_{λ′}. If K is infinite, we then have distinct n − 1 dimensional subspace W_{λ} for every λ ∈ K.

Now for the claim in the problem; our proof will be by induction on n. The n = 1 case is trivial since the W_{i} are all (0). In the general case, assume we have the claim for dimension ≤ n − 1 spaces, n ≥ 2. By the above, there are infinitely many n − 1 dimensional subspaces of V; pick W to be different from all of the W_{i}. Then W_{i} ∩W ≠ W for all i, and so each W_{i} ∩W is a subspace of W of strictly lower dimension. Thus, there is some v ∈ W which is not contained in any W_{i} ∩ W, and thus v ∈ V is not contained in any W_{i}.

Show that this is not always true if K is finite.

Solution. If Card(K) = p, then an n dimensional K-vector space has p^{n} elements. If we enumerate the vectors w_{i} and take W_{i} = Vect(w_{i}), then V = ∪_{i}W_{i}.

A.4. Let V be a K-vector space of dimension N and let W_{1} and W_{2} be two subspaces of the same dimension r ≤ n − 1. Prove that there exists a subspace U of V such that V = W_{1} ⊕ U and V = W_{2} ⊕ U.

Solution. First note that (A) if we have two spaces W_{1}, W_{2} ⊂ V of dimension strictly less than dim V, then V ≠ W_{1} ∩ W_{2}, or else Vect(V \ W_{1}) = Vect(W_{2}) = W_{2} ≠ V, contrary to A.2.

By induction on n − r. The n − r = 1 case is trivial by (A), for there is some (nonzero) v ∈ V not in either W_{i}, so take U = Vect(v). For the general case take dim W_{i} = n − k and assume the claim for n − r < k. Again by (A) there exists a vector v ∈ V that is neither in W_{i}. If we take W′_{i} = Vect(W_{i}, v) for i = 1, 2, W′_{i} are two r + 1 dimensional subspaces of V, so applying the induction hypothesis for n − r = k − 1 yields a subspace U′ ⊂ V with V = W′_{i} ⊕ U′. Let U = Vect(U′, v). Then U ∩ W_{i} = (0) because U′ ∩ W′_{i} = (0) and v ∉ W_{i}. Since V = W′_{i} ⊕ U′, W_{i} and U span V, so V = W_{i} ⊕ U.

A.5. Let V be a finite dimensional K-vector space and let u, v, w ∈ ℒ(V, V) be three endomorphisms of V. Prove the following inequalities.

(1) rk(u + v) ≤ rk(u) + rk(v)

Solution. Any vector x ∈ im(u + v) is in im(u) + im(v), for we must have x = (u + v)(y) = u(y) + v(y) ∈ im(u) + im(v) for some y ∈ V. Thus, im(u + v) ⊂ im(u) + im(v), and the above inequality then follows.

(2) rk(u + v) ≥ |rk(u) − rk(v)|

Solution. By (1), rk(v) = rk(u−(u+v)) ≤ rk(u+v)+rk(u) since obviously rk(−v) = rk(v). Thus, rk(u+v) ≥ rk(v)−rk(u). Interchanging u and v we obtain rk(u+v) ≥ rk(u)−rk(v), and the above inequality follows.

(3) inf(rk(u), rk(v)) ≥ rk(uv) ≥ rk(u) + rk(v) − dim(V)

Solution. Let the dimension of V be n. The first inequality is easy, since im(uv) ⊂ im(u) and ker(v) ⊂ ker(uv) implies

dim im(uv) = n − dim ker(uv) ≤ n − dim ker(v) = dim im(v)

For the second inequality, let A = im(v) ⊂ V and consider the restriction u|_{A} : im(v) → V. Of course, im(u|_{A}) = im(uv), but ker(u|_{A}) = A ∩ ker(u), and thus dim ker(u|_{A}) ≤ dim ker(u). This implies that

rk(uv) = rk(u|_{A}) = dim A − dim ker(u|_{A}) ≥ dim im(v) − dim ker(u) = rk(v) + rk(u) − dim(V)

(4) rk(uv) + rk(vw) ≤ rk(v) + rk(uvw)

Solution. Note that v maps ker(uv) onto ker(u) ∩ im(v); it is clear that v(ker(uv)) ⊂ ker(u) ∩ im(v), and if x ∈ ker(u) ∩ im(v), x = v(y) for some y ∈ V and v(y) ∈ ker(u) ⇒ y ∈ ker(uv) ⇒ x ∈ v(ker(uv)). The kernel of this map is, of course, ker(v) (since ker(v) ⊂ ker(uv)), so dim ker(uv) = dim ker(v) + dim ker(u) ∩ im(v). It then follows by n = dim ker(u) + rk(u) that

rk(v) − rk(uv) = dim ker(u) ∩ im(v)

and similarly

rk(vw) − rk(uvw) = dim ker(u) ∩ im(vw)

Since im(v) ⊃ im(vw), the first is greater than or equal to the second, thus

rk(v) − rk(uv) ≥ rk(vw) − rk(uvw) ⇒ rk(v) + rk(uvw) ≥ rk(uv) + rk(vw)

Use the last inequality to prove that if k ≥ 1, and u^{k} denote u × ⋯ × u (k times) then:

rk(u^{k}) ≤ \frac{1}{2} (rk(u^{k+1}) + rk(u^{k−1}))

Solution. Set v = u^{k−1}, u = w and apply (4); we get

2rk(u^{k}) ≤ rk(u^{k−1} + rk(u^{k+1})) ⇒ rk(u^{k}) ≤ \frac{1}{2} (rk(u^{k+1}) + rk(u^{k−1}))