home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18793 < prev    next >
Encoding:
Internet Message Format  |  1993-01-27  |  2.4 KB
  1. Path: sparky!uunet!portal!lll-winken!overload.lbl.gov!agate!spool.mu.edu!howland.reston.ans.net!usc!cs.utexas.edu!rutgers!igor.rutgers.edu!pepper.rutgers.edu!gore
  2. From: gore@pepper.rutgers.edu (Bittu)
  3. Newsgroups: sci.math
  4. Subject: Re: Matrices (problem)
  5. Keywords: Rank
  6. Message-ID: <Jan.26.12.43.24.1993.15862@pepper.rutgers.edu>
  7. Date: 26 Jan 93 17:43:26 GMT
  8. References: <Jan.24.22.14.31.1993.13572@inferno.rutgers.edu> <1993Jan25.154208.16365@CSD-NewsHost.Stanford.EDU>
  9. Organization: Recreation Center, Busch Campus
  10. Lines: 47
  11.  
  12. In article <1993Jan25.154208.16365@CSD-NewsHost.Stanford.EDU* rivin@SAIL.Stanford.EDU (Igor Rivin) writes:
  13.  
  14. * In article <Jan.24.22.14.31.1993.13572@inferno.rutgers.edu* gore@inferno.rutgers.edu (Bittu) writes:
  15. * >A simple question about the rank of a special matrix (this is not a
  16. * >homework problem; I already know a solution, want something better).
  17. * >In fact, this was probably on the Math Olympiad a few years ago.
  18. * >
  19. * >Let A be a matrix with the following properties:
  20. * >
  21. * >1. A is 2n+1 x 2n+1 for a positive integer n.
  22. * >
  23. * >2. A has 0's on the diagonal.
  24. * >
  25. * >3. The remaining entries are either 1's or -1's.
  26. * >
  27. * >4. Every row has exactly n 1's and n -1's.
  28. * >
  29. * >We want to show that the rank of this matrix is 2n (over complex
  30. * >numbers, say). Clearly the rank is <= 2n (all columns sum to the zero
  31. * >vector). 
  32. * 
  33. * It is not clear that the below is any more elegant than the GF[2]
  34. * solution, but here goes (m=2n+1):
  35. * 
  36. * (a) The question is equivalent to showing that the null-space of A is
  37. * generated by the vector (1, ... ,1)
  38. * 
  39. * (b) Which is equivalent to showing that there is no null-vector v of
  40. * A, such that the sum of elements of v adds up to 0.
  41. * 
  42. * (c) suppose there is such a vector V -- it is easy to see that it must
  43. * also be a null vector of the matrix B which has 0s on the main
  44. * diagonal, and 1s elsewhere (do it row by row).
  45.  
  46. This is not clear to me. If the entries of V add up to 0, then BV = -V
  47. and not 0 as you mention. If the entries of V are v(1),v(2),...,v(2n+1) 
  48. then the product of the ith row of B with V would be 
  49. v(1) + v(2) + ... + v(i-1) + v(i+1) + ... + v(2n+1) = -v(i). Therefore
  50. BV =/= 0.
  51.  
  52. --Bittu
  53.  
  54. * (d) B = -I(m) + J(m), where J has all ones. J(m) vanishes on the
  55. * orthogonal complement of the vector w=(1, ... ,1), and multiplies w by
  56. * m. hence the eigenvalues of B are (n-1, -1, ..., -1), hence it is
  57. * non-singular, hence V is the 0 vector, hence w is the only null-vector
  58. * of A, hence A has rank m-1 = 2n.
  59.