wu :: forums
wu :: forums - Sums of Dyads (9/3/2002)

Welcome, Guest. Please Login or Register.
Jul 6th, 2022, 4:14pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, Grimbal, towr, Eigenray, SMQ, william wu)
   Sums of Dyads (9/3/2002)
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Sums of Dyads (9/3/2002)  (Read 2361 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Sums of Dyads (9/3/2002)  
« on: Sep 3rd, 2002, 6:42pm »
Quote Quote Modify 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

Email

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

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board