Here is an interesting riddle on random matrices.
(Rank of Random Binary Matrix). Let denote the number of binary matrices of dimension and rank , so that by symmetry . This is a repost of the solution that I have arrived at (certainly not the first!) and submitted as part of a homework (9) problem from the doctoral course Modern coding theory (by Rudiger Urbanke) at EPFL. The sumbitted solution in PDF is available here.
Rank of a matrix is essentially the number of nonzero rows when the matrix is expressed in echelon form. So, we just need to compute the ways these matrices can be created with non zero rows. Since the elements of the matrix are binary (from ), we can simply do a counting.
It is trivial to compute for and . For , only all zero matrix possible, and only one such matrix exist. Hence . For , since , no matrix exist, which means .
Now we consider . How many ways? We have non zero rows of the matrix, which means all rows must be nonzero. Without loss of generality, for counting, we could assume that, the rows are ordered. The last row ( row can be be done in , since there anything other than all vector (of size ) is allowed. On -th row, anything other than that of row is allowed. There are ways here. -th row can have anything except any linear combination of the rows and . This is nothing but . Row then have and so on. In all, Following the same procedure, we can have a total of
ways. For , we can construct a rank matrix of size in any of the following ways:
- Take a rank matrix of size and add an independent row.
- Take a rank matrix of size and add a dependent row.
For every matrix,
and hence,
ways. (Essentially avoid all possible linear combinations of existing rows). Using the second (item 2 above) method, we can have and
different ways a rank matrix can be formed. Where,the first term () is when the all zero row is picked as the new row. In ways we can pick any one of the exisiting row as a dependent (new row). In general for we can have combination of existing rows out of in different ways to make a dependent (new) row.
So using (1) and (2) we get,
Putting everything together,
1 comment
Comments feed for this article
September 19, 2017 at 1:23 pm
qingsheng
if the two vectors are (1,1,0) and (0,1,1), how could we have 4 possible (2C0 + 2C1 + 2C2) vectors as a linear combination of them two ? Since (1,2,1) is not in the sample sapce.
How could we get the formula that the total number of linear combination is (nC0 + nC1 + nC2 + … + nCn)