2
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ There's "ith column only", or "jth row only", or variations on those based on other vectors than the standard basis vectors. $\endgroup$ – user44191 Dec 17 '18 at 9:20
  • 1
    $\begingroup$ 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). $\endgroup$ – Dirk Dec 17 '18 at 19:14
  • $\begingroup$ 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}\}$. $\endgroup$ – user44191 Dec 18 '18 at 0:17
1
$\begingroup$

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).

Toeplitz or Hankel matrices are another candidate.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bart Jansen Dec 17 '18 at 16:58
  • $\begingroup$ @BartJansen What do you mean by "nontrivially", here? $\endgroup$ – user44191 Dec 17 '18 at 19:27
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.