Linear Algebra and Analysis

8.7 Rank Of A Matrix

Proof: Suppose the determinant rank of A =

equals r. Thus some r × r submatrix has non zero determinant and there is no larger square submatrix which has non zero determinant. Suppose such a submatrix is determined by the r columns whose indices are

j1 < ⋅⋅⋅ < jr

and the r rows whose indices are

i1 < ⋅⋅⋅ < ir

I want to show that every row is a linear combination of these rows. Consider the l^th row and let p be an index between 1 and n. Form the following

× matrix

( ) | ai1j1 ⋅⋅⋅ ai1jr ai1p| || ... ... ... || |( a ⋅⋅⋅ a a |) irj1 irjr irp alj1 ⋅⋅⋅ aljr alp

Of course you can assume l

because there is nothing to prove if the l^th row is one of the chosen ones. The above matrix has determinant 0. This is because if p then the above would be a submatrix of A which is too large to have non zero determinant. On the other hand, if p ∈ then the above matrix has two columns which are equal so its determinant is still 0.

Expand the determinant of the above matrix along the last column. Let C_k denote the cofactor associated with the entry a_ikp. This is not dependent on the choice of p. Remember, you delete the column and the row the entry is in and take the determinant of what is left and multiply by −1 raised to an appropriate power. Let C denote the cofactor associated with a_lp. This is given to be nonzero, it being the determinant of the matrix r × r matrix in the upper left corner. Thus

∑r 0 = alpC + Ckaikp k=1

which implies

∑r ∑r alp = − Ck-aikp ≡ mkaikp k=1 C k=1

Since this is true for every p and since m_k does not depend on p, this has shown the l^th row is a linear combination of the i₁,i₂,

,i_r rows. ■

Proof: From Theorem 8.7.2, every row is in the span of r rows where r is the determinant rank. Therefore, the row rank (dimension of the span of the rows) is no larger than the determinant rank. Could the row rank be smaller than the determinant rank? If so, it follows from Theorem 8.7.2 that there exist p rows for p < r ≡ determinant rank, such that the span of these p rows equals the row space. But then you could consider the r ×r sub matrix which determines the determinant rank and it would follow that each of these rows would be in the span of the restrictions of the p rows just mentioned. By Theorem 3.1.5, the exchange theorem, the rows of this sub matrix would not be linearly independent and so some row is a linear combination of the others. By Corollary 8.4.2 the determinant would be 0, a contradiction. ■

Proof: This follows from the above by considering A^T. The rows of A^T are the columns of A and the determinant rank of A^T and A are the same. Therefore, from Corollary 8.7.3, column rank of A = row rank of A^T = determinant rank of A^T = determinant rank of A. ■

The following theorem is of fundamental importance and ties together many of the ideas presented above.

Proof: Suppose det

= 0. Then the determinant rank of A = r < n. Therefore, there exist r columns such that every other column is a linear combination of these columns by Theorem 8.7.2. In particular, it follows that for some m, the m^th column is a linear combination of all the others. Thus letting A = where the columns are denoted by a_i, there exists scalars α_i such that

∑ am = αkak. k⁄=m

Now consider the column vector, x ≡

^T. Then

∑ Ax = − am + αkak = 0. k⁄=m

Since also A0 = 0, it follows A is not one to one. Similarly, A^T is not one to one by the same argument applied to A^T.  This verifies that 1.) implies 2.).

Now suppose 2.). Then since A^T is not one to one, it follows there exists x≠0 such that

AT x = 0.

Taking the transpose of both sides yields

xTA = 0T

where the 0^T is a 1 × n matrix or row vector. Now if Ay = x, then

2 T ( T ) |x|= x (Ay) = x A y = 0y = 0

contrary to x≠0. Consequently there can be no y such that Ay = x and so A is not onto. This shows that 2.) implies 3.).

Finally, suppose 3.). If 1.) does not hold, then det

≠0 but then from Theorem 8.6.1 A⁻¹ exists and so for every y ∈ Fⁿ there exists a unique x ∈ Fⁿ such that Ax = y. In fact x = A⁻¹y. Thus A would be onto contrary to 3.). This shows 3.) implies 1.). ■

Proof: This follows immediately from the above theorem.