# Subspaces of real $n \times n$ matrices of dimension $O(n)$ [closed]

The set of real $$n \times n$$ matrices forms a vector space over the reals. Given any set $$S$$ of $$n \times n$$ matrices, there is a basis $$S' \subseteq S$$ of size at most $$n^2$$ such that any $$x \in S \setminus S'$$ can be written as a linear combination of elements in $$S'$$.

I am looking for a property $$\Pi$$ of matrices, such that any set of $$n \times n$$ matrices with property $$\Pi$$ has a basis of size $$O(n)$$ instead of $$n^2$$. In other words: I'm looking for subspaces of the $$n \times n$$ matrices that have dimension $$O(n)$$.

Taking $$\Pi$$ to be the the property of being a diagonal matrix works. Similarly, taking $$\Pi$$ to be the property of 'the nonzeros are restricted to at most one column' works; or more generally, considering any subset of $$O(n)$$ positions and having $$\Pi$$ require that all other positions are zeros, works. However, I am looking for less restrictive properties that yield a basis of size $$O(n)$$ for 'more interesting reasons'.

Taking $$\Pi$$ to be the positive semi-definite matrices does not work; the space of PSD matrices has dimension $$\binom{n+1}{2}$$. Are there any nontrivial properties beyond diagonality that ensure dimension $$O(n)$$?

• There's "ith column only", or "jth row only", or variations on those based on other vectors than the standard basis vectors. – user44191 Dec 17 '18 at 9:20
• The positive semi-definite matrices are a cone, not a linear subspace. If you are after subspaces, just define $n^2-n$ linear equations in the matrix entries (and that should be all there is for linear subspaces). – Dirk Dec 17 '18 at 19:14
• As I said earlier: you can use other vectors than the standard basis vectors. For example: choose a vector $\vec{v}_n \in \mathbb{R}^n$ for each $n$; then consider the family of matrices $\{A|\text{span}(A) \subseteq \mathbb{R}\vec{v}\}$. – user44191 Dec 18 '18 at 0:17

Tridiagonal matrices fit the requirement, and they are a lot more general; for instance, they do not have any trivial common eigenvector, and every matrix in $$\mathbb{R}^n$$ is similar to a tridiagonal one (possibly complex, via Jordan form).
• Thanks for the answer! Tridiagonal matrices have only $O(n)$ positions that may be nonzero, and such classes indeed have dimension $O(n)$ for simple reasons. I am still very much interested in further examples that may achieve dimension $O(n)$ nontrivially. – Bart Jansen Dec 17 '18 at 16:58
An example is the commutative sub-algebra generated by a matrix $$M$$: it has dimension less than or equal to $$n$$ because of the Cayley-Hamilton theorem. The same is true for commutative algebras with two generators: in this direction you may check this paper: http://www.csun.edu/~asethura/papers/Article_RMS_Newsletter.pdf.