Smallest eigenvalue for Gram matrix of unit norm matrices

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

• what is your norm of a matrix, and what is the inner product of two of them? Feb 17, 2019 at 23:31
• 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)$. Feb 17, 2019 at 23:44
• 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. Feb 18, 2019 at 9:40
• 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. Feb 18, 2019 at 15:22
• 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\}$. Feb 18, 2019 at 15:23