wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Sums of Dyads (9/3/2002)
        
(Message started by: william wu on Sep 3^rd, 2002, 6:42pm)

Title: Sums of Dyads (9/3/2002)
Post by william wu on Sep 3^rd, 2002, 6:42pm

Sums of Dyads

A matrix of rank 1 is called a dyad. Every matrix can be expressed as a sum of dyads. In one such expression for a matrix Z the number of dyads in its sum is just the number of nonzero elements in Z. Most matrices Z can be expressed as a sum of dyads in many different ways. Show that the minimum number of dyads in such a sum equals the rank of Z.

Title: Re: Sums of Dyads
Post by Yournamehere on Sep 4^th, 2002, 11:00pm

Let n = rank Z.

First we show that we need at least n dyads to sum to Z. Suppose the contrary, that m<n dyads (D_1, ..., D_m) can sum to Z. Since rank D_1 = 1, there is some row r_1 in D_1 such that every other row in D_1 is a multiple of r_1. Likewise there is a row r_2 in D_2 such that every other row in D_2 is a multiple of r_2, and so on up to D_m. But now consider the sum D_1+...+D_m = Z. Every row in Z is then a linear combination of the r_1 through r_m. Now construct a matrix Y with its first m rows r_1, ..., r_m and the remaining entries 0. Y must then have the same rank as Z. But by its construction, rank Y <= m < n = rank Z, a contradiction. So we need at least n dyads to sum to Z.

Now we show how to construct n dyads E_1, ..., E_n which sum to Z. Since rank Z = n, we can find n linearly independent non-zero rows of Z. Let s_1, ..., s_n be these rows. Then every row in Z is a linear combination of the s_1, ..., s_n. Let row i of Z be equal to a_i1 s_1 + a_i2 s_2 + ... + a_in s_n. Then set row i of dyad E_j to be a_ij s_j. Now row i of E_1+...+E_n is the same as row i of Z, and E_j is indeed a dyad, since all rows of E_j are multiples of some row s_j and hence rank E_j = 1. Thus the minimum number of dyads in a sum which equals Z is n.