wu :: forums - Print Page


    
      
        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 9^th, 2006, 2:29pm)

Title: Connected???
Post by desi on Feb 9^th, 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 9^th, 2006, 5:59pm

Sure. Consider the operation of adding c times row j to row i:
A' := (I + c E_i,j)*A,
where E_i,j has just a 1 in position (i,j). For t in [0,1],
f(t)=(I + ct E_i,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
[ I_r 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 10^th, 2006, 4:35am

Title: Re: Connected???
Post by Icarus on Feb 10^th, 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 P^n-1 x GL(n-1, R), where P^k 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 R^k to R^k). P^k is itself the continuous image of the k-dimensional sphere S^k 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 10^th, 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 P^n-1 x GL(n-1, R)

This can't be right: it has dimension (n-1)+(n-1)² = n(n-1), while the set of n x n matrices of rank r is a submanifold of R^{n^2} of dimension n²-(n-r)². For, if A is in GL_r, 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 10^th, 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 Rⁿ/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 A^N = 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.