wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> putnam exam (pure math) >> Connected???
(Message started by: desi on Feb 9th, 2006, 2:29pm)

Title: Connected???
Post by desi on Feb 9th, 2006, 2:29pm
Is the set of all n x n matrices of rank n-1 connected, assuming it to be a subset of R^n^2 with the usual metric

Title: Re: Connected???
Post by Eigenray on Feb 9th, 2006, 5:59pm
Sure.  Consider the operation of adding c times row j to row i:
A' := (I + c Ei,j)*A,
where Ei,j has just a 1 in position (i,j).  For t in [0,1],
f(t)=(I + ct Ei,j)*A
gives a rank-preserving continuous path from A to A'.  Thus any operation of this type keeps you within the same connected component of the set of matrices of a given rank.

Now, if A has rank r < n, then its rows are not linearly independent, so we can make one row 0 by adding a linear combination of the others.  Similarly we can also make one column 0.  By using the following operations on a pair of rows/columns:
(0, x) -> (x, x) -> (x, 0),
we may assume the last row and column are both 0.  But now we can do any elementary row/column operation on the upper-left (n-1) x (n-1) minor.  For
(x, y, 0) -> (0, y, x) -> (y, 0, x) -> (y, x, 0)
shows we can swap two rows, and we can scale a row by a non-zero c with
(x, 0) -> (x, x) -> (cx, x) -> (cx, 0).
Thus we can get any A into the form
[ Ir  O ]
[ O  O ],
and it follows that the set of matrices of a given rank r < n is connected.

The set of matrices of rank n, however, has precisely two connected components: those with det=1, and those with det=-1.

Title: Re: Connected???
Post by Grimbal on Feb 10th, 2006, 4:35am
<smart ass remark>
it's det>0 and det<0
</smart ass remark>

Title: Re: Connected???
Post by Icarus on Feb 10th, 2006, 3:59pm

on 02/09/06 at 17:59:23, Eigenray wrote:
...we may assume the last row and column are both 0.


I'm with you up to here, but after that I can't agree. That (n-1) x (n-1) minor must be invertible, since the rank of the original was matrix was n-1. Some of those minors are going to have positive determinant, and some will have negative determinant. And you cannot transform one to the other by the means you have described without passing through matrices of lower rank.

I am convinced the set has two components. It is, I believe, homeomorphic to Pn-1 x GL(n-1, R), where Pk is k-dimensional projective space, and GL(k, R) is the k-th general linear group over the field R (i.e., the set of invertible linear transformations from Rk to Rk). Pk is itself the continuous image of the k-dimensional sphere Sk under antipodal identification, and so is connected. GL(k, R) has 2 components for all k. Hence the set of nxn matrices of rank n-1 has two components as well.

Title: Re: Connected???
Post by Eigenray on Feb 10th, 2006, 5:34pm

on 02/10/06 at 15:59:33, Icarus wrote:
Some of those minors are going to have positive determinant, and some will have negative determinant. And you cannot transform one to the other by the means you have described without passing through matrices of lower rank.

Why not?  Example:
 [ 1 0 ] -> [ 1 0 ] -> [-1 0 ] -> [-1 0 ]
[ 0 0 ]    [ 1 0 ]    [ 1 0 ]    [ 0 0 ].
The extra 0 row is used as a temporary variable to make sure no rank is lost when scaling/swapping.


Quote:
I am convinced the set has two components. It is, I believe, homeomorphic to Pn-1 x GL(n-1, R)

This can't be right: it has dimension (n-1)+(n-1)2 = n(n-1), while the set of n x n matrices of rank r is a submanifold of Rn^2 of dimension n2-(n-r)2.  For, if A is in GLr, then the matrix in block form
[ A B ]
[ C D ]
has rank r iff the (n-r)x(n-r) matrix D = C A-1 B (right-multiply by
[ I  -A-1B ]
[ O  I ]),
and this can be used to define submanifold charts near each matrix of rank r.

Title: Re: Connected???
Post by Icarus on Feb 10th, 2006, 8:12pm
Found the mistake in my reasoning.

My thought was that if A is of rank k, then A induces a linear map A' on the k dimensional space Rn/ker(A). This map has a determinant d(A') which depends continuously on A.

My mistake was to believe that A' was necessarily 1-1, since the kernal of A was modded out. But this is only the case if A is not nil-potent. If AN = O for some N, then A' will not be invertible.

For example, the matrix
[ 0  0 ] = A
[ 1  0 ]
induces A' : R --> R : x -> 0.

So even though I do get a continuous map A --> d(A') into R, it is not into R*, as I had originally thought.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board