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$

closed as unclear what you're asking by Neil Hoffman, Mike Miller, Robert Bryant, Jan-Christoph Schlage-Puchta, Boris Bukh Dec 24 '18 at 16:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.

$\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.

$\endgroup$

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