# On ranks of matrices with tensor structure

Fix two $2^t$ length vector of form $p=\begin{bmatrix}u_1&v_1\end{bmatrix}\otimes\dots\otimes\begin{bmatrix}u_t&v_t\end{bmatrix}$ and $r=\begin{bmatrix}w_1&z_1\end{bmatrix}\otimes\dots\otimes\begin{bmatrix}w_t&z_t\end{bmatrix}$ where each $u_i,v_j,w_{i'},z_{j'}$ is a distinct prime.

Consider $2^r$ length vectors of form $q(x_1,y_1,\dots,x_r,y_r)=\begin{bmatrix}x_1&y_1\end{bmatrix}\otimes\dots\otimes\begin{bmatrix}x_r&v_r\end{bmatrix}$ where $x_i,y_j\in\mathbb Z$ are allowed to vary.

Consider $2T\times 2^{r+t}$ matrices of form $$\begin{bmatrix}p\otimes q(x_1^{[1]},y_1^{[1]},\dots,x_r^{[1]},y_r^{[1]})\\ p\otimes q(x_1^{[2]},y_1^{[2]},\dots,x_r^{[2]},y_r^{[2]})\\ p\otimes q(x_1^{[3]},y_1^{[3]},\dots,x_r^{[3]},y_r^{[3]})\\ \vdots\\ p\otimes q(x_1^{[T-1]},y_1^{[T-1]},\dots,x_r^{[T-1]},y_r^{[T-1]})\\ p\otimes q(x_1^{[T]},y_1^{[T]},\dots,x_r^{[T]},y_r^{[T]})\\ r\otimes q(x_1^{[T+1]},y_1^{[T+1]},\dots,x_r^{[T+1]},y_r^{[T+1]})\\ r\otimes q(x_1^{[T+2]},y_1^{[T+2]},\dots,x_r^{[T+2]},y_r^{[T+2]})\\ r\otimes q(x_1^{[T+3]},y_1^{[T+3]},\dots,x_r^{[T+3]},y_r^{[T+3]})\\ \vdots\\ r\otimes q(x_1^{[2T-1]},y_1^{[2T-1]},\dots,x_r^{[2T-1]},y_r^{[2T-1]})\\ r\otimes q(x_1^{[2T]},y_1^{[2T]},\dots,x_r^{[2T]},y_r^{[2T]}) \end{bmatrix}$$ and $$\begin{bmatrix}p\otimes q(x_1^{[1]},y_1^{[1]},\dots,x_r^{[1]},y_r^{[1]})\\ p\otimes q(x_1^{[2]},y_1^{[2]},\dots,x_r^{[2]},y_r^{[2]})\\ p\otimes q(x_1^{[3]},y_1^{[3]},\dots,x_r^{[3]},y_r^{[3]})\\ \vdots\\ p\otimes q(x_1^{[T-1]},y_1^{[T-1]},\dots,x_r^{[T-1]},y_r^{[T-1]})\\ p\otimes q(x_1^{[T]},y_1^{[T]},\dots,x_r^{[T]},y_r^{[T]})\\ q(x_1^{[T+1]},y_1^{[T+1]},\dots,x_r^{[T+1]},y_r^{[T+1]})\otimes r\\ q(x_1^{[T+2]},y_1^{[T+2]},\dots,x_r^{[T+2]},y_r^{[T+2]})\otimes r\\ q(x_1^{[T+3]},y_1^{[T+3]},\dots,x_r^{[T+3]},y_r^{[T+3]})\otimes r\\ \vdots\\ q(x_1^{[2T-1]},y_1^{[2T-1]},\dots,x_r^{[2T-1]},y_r^{[2T-1]})\otimes r\\ q(x_1^{[2T]},y_1^{[2T]},\dots,x_r^{[2T]},y_r^{[2T]})\otimes r \end{bmatrix}$$ where $(x_1^{[t]},y_1^{[t},\dots,x_r^{[t]},y_r^{[t]})$ stands for $t$th choice of $x_i,y_j$ and $T$ is a positive integer.

How large can the rank of the matrices can be if $T=2^{r+t}$ holds?

Clearly it can't exceed $2^r$ since each row is a linear function of the vector $q(...)$. To show that this upper bound is reached, we just have to show that we can take the $x,y$ such that $$Q = \begin{bmatrix} q^{[1]}\\ \vdots \\ q^{[2^r]} \end{bmatrix}$$ has full rank.
Take $[x_i, y_i] = [3^r,1]$ or $[1,3^r]$ in all possible combinations to produce $2^r$ different rows. Note that in each row the entry where all components of the form $3^r$ match is much larger than the rest. Hence $Q$ is diagonally dominant (when its rows are ordered suitably), and has full rank.
• @Freeman. To see that it is $2^{r+1}$ you can take $[u_i,v_i] = [2,a]$, where $a$ is a huge prime $a > 2*3^T$, and $r$ similarly but with $[a,2]$, and then argue similarly ($p$ and $r$ have one entry much larger than the other, so the matrix has a diagonally dominant square submatrix). Jun 18, 2018 at 7:44
• @Freeman. No. I didn't try to optimize anything in the inequalities, I just took the first thing that seemed to work. I want that $2^{r+1}\times 2^{r+1}$ matrix to be diagonally dominant, so the entry $a^{t} 3^r$ has to be larger than the sum of all other entries (which you can probably evaluate explicitly, but one of them is $3^{r-1}a^{t}$ and one is $3^{r}2a^{t-1}$). Jun 18, 2018 at 8:03