On ranks of matrices with tensor structure

Question

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?

Answer 1

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.