You are currently browsing the tag archive for the ‘modern coding theory’ tag.

Here is an interesting riddle on random matrices.

(Rank of Random Binary Matrix). Let $R(l,m,k)$ denote the number of binary matrices of dimension $l \times m$ and rank $k$, so that by symmetry $R(l,m,k)=R(m,l,k)$.  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 $G$ is essentially the number of nonzero rows when the matrix $G$ is expressed in echelon form. So, we just need to compute the ways these matrices can be created with $k$ non zero rows. Since the elements of the matrix are binary (from $\mathbb{F}_{q=2}$), we can simply do a counting.

It is trivial to compute $R(l,m,k)$ for $k=0$ and $k>l$. For $k=0$, only all zero matrix possible, and only one such matrix exist. Hence $R(l,m,0)=1$. For $l>k>0$, since $k>\min(l,m)$, no matrix exist, which means $R(l,m,k)=0$ .

Now we consider $l=k>0$.  How many ways? We have $l=k$  non zero rows of the $l\times m$  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 ( $l^{th}$ row can be be done in $2^{m}-1$,  since there anything other than all $0$ vector (of size $m$) is allowed. On $(l-1)$-th row, anything other than that of row $l$ is allowed. There are $2^{m}-2$ ways here. $l-2$-th row can have anything except any linear combination of the rows $l$ and $l-1$. This is nothing but $2^m-\left({\binom{2}{0}+\binom{2}{1}+\binom{2}{2}}\right)=2^m-2^2$. Row $l-3$ then have $2^m-\left(\binom{3}{0}+\binom{3}{1}+\binom{3}{2}\right)=2^m-2^3$ and so on. In all, Following the same procedure, we can have a total of $= \left(2^m-1\right) \left(2^m-2^1\right)\left(2^m-2^2\right)\ldots \left(2^m-2^{l-1}\right)$ $=\left(2^m-1\right) 2^{1} \left(2^{m-1}-1\right) 2^{2} \left(2^{m-2}-1\right) \ldots 2^{l-1}\left(2^{m-l+1}-1\right)$ $=2^{0} 2^{1} 2^{2} \ldots 2^{l-1}\left(2^m-1\right)\left(2^{m-1}-1\right)\left(2^{m-2}-1\right)\ldots\left(2^{m-l+1}-1\right)$ $=\prod_{i=0}^{l-1}{{2^i}\left(2^{m-i}-1\right)}$ $=\prod_{i=0}^{l-1}{\left(2^{m}-2^{i}\right)}$ $=\prod_{i=0}^{l-1}{2^m \left(1-2^{i-m}\right)}$ $=2^{ml} \prod_{i=0}^{l-1}{ \left(1-2^{i-m}\right)}$

ways.  For $l>k>0$, we can construct a rank $k$ matrix of size $l \times m$ in any of the following ways:

1.  Take a rank $k-1$ matrix of size $(l-1) \times m$ and add an independent row.
2.  Take a rank $k$ matrix of size $(l-1) \times m$ and add a dependent row.

For every $(l-1) \times m$ matrix, $2^{m}-1+\binom{k-1}{1}+\binom{k-1}{2}+\ldots +\binom{k-1}{k-1}=\left(2^m-2^{k-1}\right)$

and hence, $R(l-1,m,k-1) \left(2^m-2^{k-1}\right)= R_{1}(l,m,k)$

ways. (Essentially avoid all possible linear combinations of existing $k-1$ rows).  Using the second (item 2 above) method, we can have $1+\binom{k}{1}+\binom{k}{2}+\ldots +\binom{k}{k} = 2^k$ and $R_{2}(l,m,k)= 2^k R(l-1,m,k)$

different ways a rank $k$ matrix can be formed. Where,the first term ( $=1$) is when the all zero row is picked as the new row. In $\binom{k}{1}$ ways we can pick any one of the exisiting row as a dependent (new row). In general for $0\le j\le k$ we can have combination of $j$ existing rows  out of $k$ in $\binom{k}{j}$ different ways to make a dependent (new) row.

So using (1) and (2) we get, $R(l,m,k)=2^k R(l-1,m,k)+\left(2^m-2^{k-1}\right)R(l-1,m,k-1)$

Putting everything together, $R(l,m,k) = \begin{cases} 1, & k=0, \\2^{ml} \displaystyle \prod_{i=0}^{l-1}{ \left(1-2^{i-m}\right)} , & l=k>0 \\ 2^k R(l-1,m,k) + \left(2^m-2^{k-1}\right) R(l-1,m,k-1) &l>k>0 \\ 0 & k>l>0 \end{cases}$

### Recent Comments qingsheng on Rank of a random binary m… Shammi on Yesudas and Rafi singing same… Shammi on Yesudas and Rafi singing same… Surendran Nambiath (… on Yesudas and Rafi singing same… Surendran Nambiath (… on Yesudas and Rafi singing same…

### Follow Blog via Email

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 86 other followers