home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18720 < prev    next >
Encoding:
Internet Message Format  |  1993-01-25  |  1.5 KB
  1. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!newsserver.jvnc.net!rutgers!igor.rutgers.edu!inferno.rutgers.edu!gore
  2. From: gore@inferno.rutgers.edu (Bittu)
  3. Newsgroups: sci.math
  4. Subject: Matrices (problem)
  5. Keywords: Rank
  6. Message-ID: <Jan.24.22.14.31.1993.13572@inferno.rutgers.edu>
  7. Date: 25 Jan 93 03:14:32 GMT
  8. Organization: Recreation Center, Busch Campus
  9. Lines: 30
  10.  
  11. A simple question about the rank of a special matrix (this is not a
  12. homework problem; I already know a solution, want something better).
  13. In fact, this was probably on the Math Olympiad a few years ago.
  14.  
  15. Let A be a matrix with the following properties:
  16.  
  17. 1. A is 2n+1 x 2n+1 for a positive integer n.
  18.  
  19. 2. A has 0's on the diagonal.
  20.  
  21. 3. The remaining entries are either 1's or -1's.
  22.  
  23. 4. Every row has exactly n 1's and n -1's.
  24.  
  25. We want to show that the rank of this matrix is 2n (over complex
  26. numbers, say). Clearly the rank is <= 2n (all columns sum to the zero
  27. vector). 
  28.  
  29. Let I_m be the m x m identity matrix and J_m be the all 1's matrix.
  30. The solution I know involves showing that the matrix J_m - I_m has
  31. rank m if m is even and m-1 if m is odd (over GF[2]; done by showing
  32. that its determinant is (-1)^(m-1) . (m-1)). We are only interested
  33. in the case where m is odd. We now use the well-known result that if
  34. the rank is m-1 over GF[2], it is m-1 over rationals, reals, complexes
  35. etc. Note that J_{2n+1} - I_{2n+1} is the same as A over GF[2].
  36.  
  37. I am sure there is a much easier and elegant proof of this (for the
  38. field of complexes). Any takers?
  39.  
  40. --Bittu
  41.