1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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). $\endgroup$ – Federico Poloni Jun 18 '18 at 7:44
  • $\begingroup$ @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}$). $\endgroup$ – Federico Poloni Jun 18 '18 at 8:03

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.