NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/sci/math/18723

Text File | 1993-01-25 | 1.9 KB | 52 lines

Newsgroups: sci.math
Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!SAIL.Stanford.EDU!rivin
From: [e-mail] (Igor Rivin)
Subject: Re: Matrices (problem)
Message-ID: <[e-mail]>
Keywords: Rank
Sender: [e-mail]
Organization: Computer Science Department,  Stanford University.
References: <[e-mail]>
Date: Mon, 25 Jan 1993 15:42:08 GMT
Lines: 39

In article <[e-mail]> [e-mail] (Bittu) writes:
>A simple question about the rank of a special matrix (this is not a
>homework problem; I already know a solution, want something better).
>In fact, this was probably on the Math Olympiad a few years ago.
>
>Let A be a matrix with the following properties:
>
>1. A is 2n+1 x 2n+1 for a positive integer n.
>
>2. A has 0's on the diagonal.
>
>3. The remaining entries are either 1's or -1's.
>
>4. Every row has exactly n 1's and n -1's.
>
>We want to show that the rank of this matrix is 2n (over complex
>numbers, say). Clearly the rank is <= 2n (all columns sum to the zero
>vector).

It is not clear that the below is any more elegant than the GF[2]
solution, but here goes (m=2n+1):

(a) The question is equivalent to showing that the null-space of A is
generated by the vector (1, ... ,1)

(b) Which is equivalent to showing that there is no null-vector v of
A, such that the sum of elements of v adds up to 0.

(c) suppose there is such a vector V -- it is easy to see that it must
also be a null vector of the matrix B which has 0s on the main
diagonal, and 1s elsewhere (do it row by row).

(d) B = -I(m) + J(m), where J has all ones. J(m) vanishes on the
orthogonal complement of the vector w=(1, ... ,1), and multiplies w by
m. hence the eigenvalues of B are (n-1, -1, ..., -1), hence it is
non-singular, hence V is the 0 vector, hence w is the only null-vector
of A, hence A has rank m-1 = 2n.