How many matrices can be spectrally balanced simultaneously?

Abstract

We prove that any $\ell$ positive definite $d\times d$ matrices, $M_1,\dots ,M_{\ell }$, of full rank, can be simultaneously spectrally balanced in the following sense: for any $k<d$ such that $\ell \le \lfloor \frac{d-1}{k-1}\rfloor$, there exists a matrix $A$ satisfying $\frac{{\lambda }_1(A^T{M}_{i}A)}{\mathrm{Tr}(A^T{M}_{i}A)}<\frac{1}{k}$ for all $i$, where ${\lambda }_1(M)$ denotes the largest eigenvalue of a matrix $M$. This answers a question posed by Peres, Popov and Sousi and completes the picture described in that paper regarding sufficient conditions for transience of self-interacting random walks. Furthermore, in some cases we give quantitative bounds on the transience of such walks.