Author 
Topic: Sums of Dyads (9/3/2002) (Read 2351 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Sums of Dyads (9/3/2002)
« on: Sep 3^{rd}, 2002, 6:42pm » 
Quote Modify

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.

« Last Edit: Sep 16^{th}, 2002, 2:01pm by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



Yournamehere
Guest

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 nonzero 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.


IP Logged 



