# Characterization of the subspaces of $\mathbb R^{m\times n}$ induced by rank-1 matrices?

Consider a linear subspace $$S$$ of the space of $$m\times n$$ real valued matrices $$\mathbb R^{m\times n}$$.

When does $$S$$ admit a basis consisting only of rank-1 matrices?

I.e. is there a simple criterion or algorithm to check for the existence of such a basis?

Background:

I would also be interested in the case when we also allow diagonal, permutation, or generally sparse matrices. This is because the matrix vector product $$A\cdot x$$, which usually costs $$O(n^2)$$ to evaluate, can be computed in $$O(n)$$ for the aforementioned matrix types. Thus, if we have a subspace $$S\le \mathbb R^{m\times n}$$ with $$\dim(S)\ll m\times n$$ we can potentially achieve huge performance gains by representing parametrized matrices in $$S$$ using a basis which only consists of these "cheap" matrices.

Formulation as an optimization problem:

Given a finite set of $$m\times n$$ real-valued matrices $$\mathcal A = \{A_1,\ldots, A_d\}\subset \mathbb R^{m\times n}$$, find

$$\min_{\mathcal B = \{B_1, \ldots, B_d\}\subset \mathbb R^{m\times n}} \sum_{i=1}^d \text{rank}(B_i) \qquad\text{s.t.}\quad\big\langle \mathcal A\big\rangle = \big\langle \mathcal B\big\rangle$$

Is there any hope of solving this problem exactly? If not, what types of optimization algorithms are suitable for this kind of problem, given that both the objective function and the constraint are discontinuous?

Example: given

$$S= \left\langle \underset{A_1}{\begin{bmatrix}4 & 5 & 6 \\ 7 & 9 & 11 \end{bmatrix}}, \underset{A_2}{\begin{bmatrix}2 & 3 & 4 \\ 5 & 7 & 9 \end{bmatrix}} \right\rangle$$

We can represent $$S$$ equivalently as

$$S= \left\langle \underset{B_1}{\begin{bmatrix}3 & 4 & 5 \\ 6 & 8 & 10 \end{bmatrix}}, \underset{B_2}{\begin{bmatrix}1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}} \right\rangle = \left\langle \underset{u_1v_1^T}{\begin{bmatrix} 1 \\ 2 \end{bmatrix}\begin{bmatrix}3 & 4 & 5\end{bmatrix}}, \underset{u_2v_2^T}{\begin{bmatrix} 1 \\ 1 \end{bmatrix}\begin{bmatrix} 1 & 1 & 1\end{bmatrix}}\right\rangle$$

Because $$A_1=u_1v_1^T + u_2v_2^T$$ and $$A_2 = u_1v_1^T - u_2v_2^T$$.

Now consider a parametrized matrix $$C$$ in $$S$$. If we express $$C$$ in the basis $$A$$, i.e. $$C = \lambda_1 A_1 + \lambda_2 A_2$$, then computing the matrix vector product $$C\cdot x$$ will cost us at least 16/10 multiplications/additions, whereas if we represent it in the basis $$B$$, i.e. $$C=\lambda_1 u_1v_1^T + \lambda_2 u_2v_2^T$$, then the matrix-vector product $$C\cdot x$$ can be done in 12/8 multiplications/additions.

More generally, for a space of dimension $$d$$ the scaling is $$O(dmn)$$ for a dense basis and $$O(d(m+n))$$ for a rank-1 basis in terms of both elementary multiplications and additions. (using elementary matrix multiplication)

• Am I missing something, or why is the set of matrices of one $1$ and the rest zero not always a basis? Jun 14, 2021 at 10:59
• @Toffomat I added an example to clarify the problem. Jun 14, 2021 at 11:17
• I think I solved the problem in the special case where $m,n \le 2$. Is this worth an answer? Jun 18, 2021 at 14:12
• @MorganRodgers The $2 \times 2$ case is still interesting in my opinion. There the property boils down for the subspace to be positive or negative definite. Jun 18, 2021 at 14:30

The sparse basis case is basically equivalent to the "matrix sparsification" problem. It is NP-hard to even approximate the sparsest basis for a linear space (see https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.450&rep=rep1&type=pdf). So under the widely believed assumption that P$$\neq$$NP, there is no efficient algorithm for the case of sparse matrices.