2
$\begingroup$

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.

$\endgroup$

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.