Appendix A June 7

this is installed, do not edit Appendix A : Proof that matrix rank is the number of independent columns and rows Shilov proves this but the proof is a bit spread out over several sections. Here we provide an alternative proof that is perhaps more direct. Recall the definition (1.5) of the rank of a matrix : Definition: The rank r of an m x n matrix A is the size of the largest non-vanishing subdeterminant (minor) within A. [Shilov 1.92 ] Thus, r ≤ min(m,n). (1.5) One Theorem (A.1) is established, the rest is easy. Theorem. If all kxk minors in k columns of matrix A vanish, the k columns are linearly dependent. (A.1) Contrapositive: If k columns are linearly independent, they must contain at least one non-zero kxk minor. Proof: Assume matrix A has m rows and n columns. In order for kxk minors to exist, one must have k ≤ min(m,n). Gather up the k columns and make them be the leftmost k columns of a new matrix B. Since these columns have m elements, and since k ≤ m, add m-k arbitrary new columns to the right of the k columns so that matrix B is then a square matrix. On the left below we show the k columns taken from matrix A in red, and then the arbitrary added columns are shown in blue. Consider now the process of computing det(B) by going down the rightmost column using the standard cofactor sum formula. This det(B) is a linear combination of (m-1)x(m-1) minors all in the left m-1 columns. Consider one of these minors. If we evaluate it using the same cofactor formula (of one less dimension), it will be a linear combination of (m-2)x(m-2) minors in the left m-2 columns. We keep going until we are evaluating a set of kxk cofactors in the left k columns. But these all vanish by the theorem premise. Thus, reversing this stack we conclude that det(B) = 0. The picture on the right above shows one minor at each level of the descent just described (red dot goes with red minor, etc). Now suppose it were possible that the k red columns were independent. Since the added blue columns are arbitrary, we could certainly find a set of added blue columns so that all m columns were independent. But then we would have det(B) ≠ 0. But we just showed that det(B) = 0, so it must not be possible to have the k red columns be independent, so they must be dependent. QED. Theorem. Rank(A) = r A has r linearly independent columns. (A.2) Proof: If rank(A) = r, A must have at least one non-vanishing rxr minor. The r columns of this minor are therefore linearly independent (each of these mini-columns has r elements). This means that the r full columns containing these mini-columns are also independent (see * below). So matrix A has at least r independent columns. Now let k = r+1. We know that all kxk minors in A vanish. By Theorem A.1, any set of k columns must be linearly dependent. Since k = r+1, any r+1 columns are linearly dependent, so the number of independent columns is r. * Since the mini-columns Ci are independent, one cannot write ΣiλiCi = 0 (with at least one λj ≠ 0). If the corresponding full columns ci were dependent, one could write Σiλici = 0. But if Σiλici = 0, then one must have ΣiλiCi = 0 since the latter is just a subset of the former equation set. But ΣiλiCi = 0 says that the mini-columns are dependent, which they are not. Thus, one cannot write Σiλici = 0 and thus the full columns are independent. Theorem. A has r linearly independent columns Rank(A) = r (A.3) Proof: If there are r linearly independent columns, then at least one rxr minor within those columns must be non-zero (contrapositive of Theorem A.1). Suppose there were an (r+k)x(r+k) non-vanishing minor. Then the r+k mini-columns of that minor would be independent, and thus there would be r+k independent full columns. But the theorem premise says there are only r independent columns, so all minors larger than rxr must vanish. Therefore rank(A) = r. Making trivial replacements in the above three theorems and proofs (column → row, leftmost → topmost and so on), one finds that all three theorems are valid for rows as well as columns. Thus: Theorem. If all kxk minors in k rows of matrix A vanish, the k rows are linearly dependent. (A.4) Theorem. Rank(A) = r A has r linearly independent rows. (A.5) Theorem. A has r linearly independent rows Rank(A) = r (A.6)