2
$\begingroup$

Given $n$ symmetric matrices $A_1, \dots, A_n \in \mathbb{R}^{k\times k}$, such that $\|A_i\| \leq 1$ for all $i$, we consider the matrix $M \in \mathbb{R}^{n\times n}$, where $M_{ij} = \langle A_i, A_j\rangle$.

We are interested in upper bounding the smallest eigenvalue of $M$. In general we have the obvious upper bound of $O(k)$. Also, whenever $n > k^2$, the upper bound is $0$ since $rank(M) \leq k^2$.

Can we say anything interesting whenever $k \leq n \leq k^2$? More precisely, can we show that within this interval the upper bound on the smallest eigenvalue decays like $k / f(n/k)$ for some monotonely increasing $f$ (think for instance $f(x) = \sqrt{x}$)?

Improve this question
$\endgroup$
7
  • $\begingroup$ what is your norm of a matrix, and what is the inner product of two of them? $\endgroup$
    – Will Jagy
    Commented Feb 17, 2019 at 23:31
  • $\begingroup$ Here, matrix norm is operator norm induced by $\ell_2$ norm, i.e. for all matrices we have $\|A_i x\|_2 \leq \|x\|_2$ for all $x$. Inner product is pointwise inner product, $\langle A, B \rangle = \sum_{i,j} A_{ij} B_{ij} = tr(A^\top B)$. $\endgroup$
    – zotachidil
    Commented Feb 17, 2019 at 23:44
  • 1
    $\begingroup$ I do not think anything interesting can be said if $k \leq n \leq k^2$. Indeed, if $A_1,\dots,A_n$ are orthogonal matrices which are pairwise orthogonal for the scalar product $\langle \cdot,\cdot\rangle$, then $M$ is the matrix $k 1$, so its smallest eigenvalue is $k$. And there are infinitely many $k$'s (eg the powers of two, perhaps even every $k$?) for which you can find such a family for $k=n^2$ (ie an orthogonal basis of $\mathbb{R}^{k \times k}$ made of orthogonal matrices). So for such $k$, the best upper bound if $k$ if $n\leq k^2$ and $0$ otherwise. $\endgroup$
    – Mikael de la Salle
    Commented Feb 18, 2019 at 9:40
  • 1
    $\begingroup$ For $k=2$, take the matrices $\begin{pmatrix} 1 & 0 \\ 0 &1\end{pmatrix}, \begin{pmatrix} 1 & 0 \\ 0 &-1\end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 1 &0\end{pmatrix}, \begin{pmatrix} 0 & 1 \\ -1 &0\end{pmatrix}$. For $k$ a power of two, take tensor products of this basis. $\endgroup$
    – Mikael de la Salle
    Commented Feb 18, 2019 at 15:22
  • 1
    $\begingroup$ If you allow complex entries and unitary matrices, you can obtain such an orthogonal basis made of unitary matrices: $U_{a,b} = (1_{s-t = a \mod k} e^{2ib s \pi/n})_{1 \leq s,t \leq k}$ for $a,b \in \{1,\dots,k\}$. $\endgroup$
    – Mikael de la Salle
    Commented Feb 18, 2019 at 15:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .