1
$\begingroup$

I'm looking for (the best) lower bounds on the row rank of the following type of matrix. In other words, for a matrix of $n$ columns, we can state the row rank of the matrix as $\Omega(f(n))$ for some $f(n)$.

$$ \begin{array}{cc|ccc|ccccc|c} 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & \dots \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & \dots \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & \dots \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & \dots \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & \dots \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & \dots \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$

I tried to make it as clear as possible, but essentially, we have the left 2 columns are $I_2$, the identity matrix of size 2, repeated over and over. The next 3 columns are $I_3$ repeated over and over, the next 5 $I_5$ over and over, and so on. In general, it repeats $I_\text{$p$th prime}$ over and over. In other words, we have:

$$ \begin{array}{c|c|c|c|c|c} I_2 & I_3 & I_5 & I_7 & I_{11} & \dots \\ I_2 & I_3 & I_5 & I_7 & I_{11} & \dots \\ I_2 & I_3 & I_5 & I_7 & I_{11} & \dots \\ \vdots &\vdots &\vdots &\vdots &\vdots & \ddots \end{array} $$

I'm trying to find a function $f(n)$, that, for a matrix of $n$ columns, we are guaranteed that the matrix has column rank at least $f(n)$.

We can assume that it has $n$ columns, with $n$ the sum of the first $p$ primes, and $\displaystyle \prod_{k=1}^p{ (\text{$p$th prime}) }$ rows - the product of the first $p$ primes.

$\endgroup$
10
  • $\begingroup$ Is this an infinite matrix, or do you stop at some prime? $\endgroup$ – Ben Grossmann Oct 20 '16 at 13:50
  • $\begingroup$ @Omnomnomnom: It's a finite matrix - it has $n$ columns, and we can assume it has $2 \cdot 3 \cdot 5 \cdot 7 \cdots p$ rows, for some prime $p$. I'll edit the question to make it more clear. $\endgroup$ – Matt Groff Oct 20 '16 at 13:56
  • $\begingroup$ and may we assume that $2\cdot3 \cdot \cdots \cdot p \ge n$? $\endgroup$ – John Hughes Oct 20 '16 at 13:57
  • $\begingroup$ @JohnHughes: Yes, you may assume $2 \cdot 3 \cdots p \ge n$. $\endgroup$ – Matt Groff Oct 20 '16 at 14:05
  • $\begingroup$ It sure looks to me as if two things, taken together, might show that it's got maximal rank: first, that if some real linear combination of 0/1 vectors is zero, then some rational linear combination is as well (and hence, mutliplying by the gcd, so is some integer combination), and second, an application of the chinese remainder theorem. I don't know how to prove the first offhand (a gaussian elimination argument maybe?) and I don't see exactly how to make the second work...but it might get you somewhere. $\endgroup$ – John Hughes Oct 20 '16 at 15:21
2
$\begingroup$

Partial answer: An easy way to see that you lose at least one dimension of rank each time you add a new $p \times p$ block: add the first col to the second (which is invertible, as are all other ops I'm gonna describe, so they don't change the rank). Add the third column to the 4th, and then the 4th to the 5th. Add the 6th to the 7th, te 7th to the 8th, etc. (i.e., form cumulative sums of the columns within each $p \times p$ block.

Notice that in each case the last column consists of all "1"s, hence the last column in the "3" block is redundant with the last column in the 2-block, so it doesn't increase the rank; similarly for the last col in the 5 block, etc.

An alternative way to see this: look at the vector $(1, 1, -1, -1, -1)^t$ and mutliply this on the left by the matrix that has the $p = 2, 3$ blocks in it. It'll give you all zeros. For the $p = 2, 3, 5$, you can use $(1,1, -1, -1, -1, 0,0,0,0,0)^t$ and $(1, 1, 0,0,0, -1, -1, -1,-1,-1)$ and get the same effect. In short, I'm giving you a recipe for constructing what I believe is a basis for the nullspace of each matrix.

I don't yet see how to turn this into a recipe for showing that the remaining columns are independent, however, so I've given you an upper bound, but not a lower one which is (alas) what you requested.

Two thoughts:

  1. it might be that the rank is as large as you expect even when you consider the matrix as having entries in Z/2Z; doing row/col operations in that case is somewhat easier, however.

  2. It's pretty easy to write down vectors orthogonal to the things I've claimed are in the nullspace (just put in an appropriate number of +/- signs!), and if you're clever, maybe you can make them pairwise orthogonal as well. In that case, projecting the image onto the space that they span should preserve rank, and the projection matrix (up to scale) is easy to write down (just use those vectors as rows of $B$, and compute $BA$, where $A$ is your original matrix). And then it might be obvious that $BA$ is full-rank, if, for example, it ends up upper-triangular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.