Author |
Topic: Sums of Dyads (9/3/2002) (Read 2436 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Sums of Dyads (9/3/2002)
« on: Sep 3rd, 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 16th, 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 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove