Suppose $\mathbf{B}\in\left[0,1\right]^{T\times M}$ is a binary matrix, $\mathbf{B}_{i}$ is a column of $\mathbf{B}$, and $\mathbf{X}\in\mathbb{R}^{N\times T}$ is a matrix where the columns are vectors in general position (as a result, any subset of $N$ columns are linearly independent). Furthermore, assume that $$\max\left(M,N\right)<T<MN .$$

Please find sufficient and necessary conditions (otherwise, very general sufficient conditions) on $\mathbf{B}$ such that the $NM\times T$ matrix $$ \mathbf{A}=\left(\begin{array}{c} \mathbf{X}\mathrm{diag}\left(\boldsymbol{\mathbf{B}}_{1}\right)\\ \mathbf{X}\mathrm{diag}\left(\mathbf{B}_{2}\right)\\ \vdots\\ \mathbf{X}\mathrm{diag}\left(\mathbf{B}_{M}\right) \end{array}\right) $$ has the full rank - $T$. As usual, $\mathrm{diag}\left(\mathbf{B}_{i}\right)$ is a diagonal matrix with $\mathbf{B}_{i}$ in its diagonal.

Three comments:

1) Suppose the components $B_{t,i}$ are randomly and independently drawn $\forall i,t$ from a Bernoulli distribution with parameter $p$. Then in numerical simulations I'm getting that typically $\mathbf{A}$ has a full rank if $$ \min\left(p,1-p\right)NM > T. $$ However, if possible, I prefer not to have strong distributional assumptions on $\mathbf{B}$. Assuming $NM\gg T$ is OK though.

2) Suppose we define the overlap $K$ as the maximal number of rows $\left\{ t_{k}\right\} _{k=1}^{K}$, in which $\forall i:B_{t_{k},i}=B_{t_{1},i}$. Then $K\leq N$ is a necessary condition for $\mathbf{A}$ being full rank - since if $K>N$ then the $\left\{ t_{k}\right\} _{k=1}^{K}$ columns of $\mathbf{A}$ are dependent. Unfortunately, this is not a sufficient condition.

3) A rather general sufficient condition is that (1) $\forall i:$ $\sum_{t=1}^T B_{t,i}\leq N$ and (2) $\forall t:$ $\sum_{i=1}^N B_{t,i} > 0$. However, I would like it relax condition (1), if possible. The numerical results above indicate this should be possible.

Thanks in advance! Any help would be appreciated.


Your Answer

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

Browse other questions tagged or ask your own question.