wu :: forums « wu :: forums - Sums of Dyads (9/3/2002) » Welcome, Guest. Please Login or Register. Feb 8th, 2023, 1:31pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums  riddles  putnam exam (pure math) (Moderators: Grimbal, SMQ, william wu, Eigenray, Icarus, towr)  Sums of Dyads (9/3/2002) « Previous topic | Next topic » Author Topic: Sums of Dyads (9/3/2002)  (Read 2382 times)
william wu       Gender: Posts: 1291 Sums of Dyads (9/3/2002)   « on: Sep 3rd, 2002, 6:42pm » Quote Modify

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  Re: Sums of Dyads   « Reply #1 on: Sep 4th, 2002, 11:00pm » Quote Modify Remove

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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »