Evaluating the rank of combined binary circulant matrices

1. Apr 2, 2012

shab1

Hey all,

Say I have the following three binary circulant matrices #1(2*10) , #2(3*10) and #3(4*10) as shown below. All these matrices are essentially full rank.

#1:
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1

#2:
1 0 0 1 0 0 1 0 0 1
0 1 0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0 1 0

#3:
1 0 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0

Now, if I combine these matrices by stacking them one on top of the other as shown below to form a larger matrix (9*10), I see that the resultant matrix is not circulant and not full rank. However, the lower bound on the rank of this combined matrix is always equal to the number of constituent circulant matrices times the rank of the minimum rank constituent circulant matrix (in this case it's 2 for the #1 matrix and so the rank of the combined matrix will be greater than or equal to 2*3=6). However, I don't have any analytical reasoning to prove this empirical finding. Can someone please help me prove this result analytically.

Combined matrix (9*10)
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 0 1 0 0 1 0 0 1
0 1 0 0 1 0 0 1 0 0
0 0 1 0 0 1 0 0 1 0
1 0 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0
0 0 0 1 0 0 0 1 0 0

Please note that the number of columns is irrelevant as long as it is greater than the number of rows which is always the case in my experimental setup. Also, this result holds for any number of constituent circulant matrices with any number of rows as long as the combined matrix is formed in the way described and shown above. For e.g. the individual circulant matrices may have the dimensions 4*20, 7*20 and 8*20 to form a 19*20 combined matrix. I just need to come up with a mathematical proof of what would be the lower bound on the rank of such a combined matrix.

Best!