Shilov notes

Shilov Notes PhL 6.7.15 Section 3.12 (a1) Claim: if the rank of a matrix is less than number of columns, columns are linearly dependent. Shilov claims this is obvious based on a,b,c of Section 2.54. Remember that rank has the basis minor definition. Is this claim obvious to ME ? Not really! Suppose rank is r, and let's put the "basis minor" (the at least one det rxr ≠ 0) in the upper left corner. Here we have rank = 3 and there are 5 rows. Fig 1 Since red rxr det ≠ 0. the three short Ci shown are linearly independent. My "simple theorem" shows that therefore the three full ci are also linearly independent. But this really has no bearing on the claim (a). I think the relevant theorem is this from page 37 I have read through the proof of this theorem and it seems good. A "basis column" is one of the columns that passes through the "basis minor" which is read above. In terms of the picture above, obviously any of the first r full columns ci can be written as a lincom of the first r ci! For example, ci = ci. The main idea of the theorem is that this is also true for all the OTHER columns! They can all be written as lin com of the first r full columns. Within this context, now think about claim (a). If there are more columns than rank, then all the extra columns are lin dep on the basis columns. Even if the matrix had only one extra column, the columns would be lin dep. It cannot have NO extra columns because claim is that rank < # columns. That would be this situation: Fig 2 For this matrix, the max rank is obviously 3, and the premise of (a) is that # columns > 3. So I claim that the proof of (a) really depends on this Basis Minor Theorem. (a2) Claim: if the rank of a matrix equals the number of columns, columns are lin indep. This is true due to my "simple theorem" which says Ci lin indep ci lin indep, so I am happy here. (b) Claim: any r+1 columns are lin dep. Well, for r+1 columns to exist, picture looks like Fig 1. We already know that all cols are lin combs of the first r columns, so if you pick any set of r+1, the extra one is a lincomb, so r+1 set is lin dep, no problemo. (c) Claim: the rank of a matrix equals the number of lin indep columns. Well this claim is the Biggie. He says this is obvious, do I think if is obvious? Suppose the rank is r. Then I know Fig 1 and the simple theorem that the first r ci are lin indep. so I know that column rank ≥ r since I already have a set of r lin-indep columns. But any other column is lindep, so we know that all sets of r+1 columns are dep. Thus, column rank = r. Yes indeedy. ************************************ Conjectured Theorem 1: Imagine two 3 vectors a and b. Suppose all three 2x2 minors vanish. Then claim that these vectors must be dependent. Proof: Create 3x3 matrix (a,b,c) by adding an arbitrary third vector c. Since all 2x2 minors of a,b vanish, we know that det (a,b,c) = c1 minor1 + c2 minor2 + c3minor3 = 0 since the 3 minors are zero. So we have a set of vectors (a,b,c) which are lin dep for ANY vector c. Suppose a and b were lin indep. I could surely find a vector c such that (a,b,c) are lin dep. Perhaps c = a x b. This would imply det(a,b,c) ≠ 0 for that particular c. But we just set det(a,b,c) = 0. Thus, a and b cannot be lin indep. This seems good! Conjectured Theorem 2: Imagine two 4 vectors a and b. Suppose all 2x2 minors vanish. Then claim that these vectors must be dependent. Proof: Add two more arbitrary columns c and d. To evaluate det (a,b,c,d), work down column d. This involves 3x3 dets among the first 3 columns. But each of those 3x3 dets = 0 by working each of them down column c. Thus, det(a,b,c,d) = 0 for any c and d. If a and b are indep, can certainly find c,d so the set of four a,b,c,d are lin indep. But then det(a,b,c,d) ≠ 0 which is a contradiction. I think this generalizes so I have now proven this fact: Conjectured Theorem 3: Consider a matrix two of whose columns are a,b and all 2x2 minors for these columns are 0. Then a and b are dependent. Conjectured Theorem 4: Consider three 4-vectors a,b,c such that all 3x3 minors are 0. Then a,b,c are dependent. Proof. Add a fourth column d, arbitrary. Then evaluate det down d column so det(a,b,c,d) = 0. But could certainly choose d indep if a,b,c are indep. But then det(a,b,c,d) ≠ 0, contradiction. So a,b,c cannot be indep. Conjectured Theorem N. Consider a matrix and suppose for a,b all 2x2 minors are 0. Then any determinant larger than 2x2 which involves includes these two columns vanishes. But not a really useful theorem. Theorem A. If all kxk minors within k columns of matrix A vanish, the k columns are linearly dependent. 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 installed k columns in red, and then the arbitrary added columns 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 any 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 B. Rank(A) = r A has r linearly independent columns. Proof: Matrix 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 then 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 C. A has r linearly independent columns Rank(A) = r Proof: If there are r linearly independent columns, then at least one rxr minor associated with those columns must be non-zero. This follows from Theorem A, since if there were no non-zero rxr minors, those r columns would have to be dependent. 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 various 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 A: If all kxk minors within k rows of matrix A vanish, the k rows are linearly dependent. Theorem B+C: Rank(A) = r A has r linearly independent rows. . Let k ≡ r+1. Then all kxk minors in matrix A vanish. By Theorem A, any set of k columns is linearly dependent.