Suppose that $M$ is a $3$ by $2$ matrix in which every $2$ by $2$ submatrix is invertible. Is it true that $M$ always has a $2$ by $2$ submatrix $M_{1}$ such that $\left\Vert M_{1}\right\Vert ^{2}\left\Vert M_{1}^{-1}\right\Vert ^{2}\lambda_{2}\left(MM^{T}\right)\ge\left\Vert M\right\Vert ^{2}$ where $\left\Vert \cdot\right\Vert $ is the norm of a matrix (refer to here for the definition) and $\lambda_{2}\left(\cdot\right)$ is the second largest eigenvalue of a $3$ by $3$ symmetric matrix? Thanks
Is this true for $3$ by $2$ matrices?
-
0@peanae: A link is given for the definition of the norm, but the definition linked to is dependent on which norm is given to $\mathbb C^n$, which is not specified above. Are we to presume that $\mathbb C^n$ has the Euclidean norm? – 2013-07-24
1 Answers
The answer is affirmative. Your inequality is equivalent to $\sigma_1(M_1)/\sigma_2(M_1)\ge\sigma_1(M)/\sigma_2(M)$, where $\sigma_i(X)$ denotes the $i$-th largest singular value of a matrix $X$. We can actually prove a more general proposition:
Proposition. Suppose $n\ge1$ and every $n\times n$ submatrix of some $M\in\mathbb{C}^{(n+1)\times n}$ is invertible. Then there exists an $n\times n$ submatrix $M_1$ of $M$ such that $\sigma_1(M_1)/\sigma_n(M_1)\ge\sigma_1(M)/\sigma_n(M)$.
Proof. Denote the $n+1$ rows of $M$ by $b_1^\ast, \ldots, b_{n+1}^\ast$. Let $B_i=\sum_{k\not=i} b_kb_k^\ast$. Then each $B_i$ corresponds to a product of the form $M_1^\ast M_1$ where $M_1$ is the submatrix obtained by deleting the $i$-row of $M$. We have $\sum_i B_i=nM^\ast M$ and $ \frac{\sigma_1^2(M)}{\sigma_n^2(M)} =\frac{\max_{\|u\|=1} u^\ast M^\ast Mu}{\min_{\|v\|=1} v^\ast M^\ast Mv} =\frac{\max_{\|u\|=1} \sum_i u^\ast B_iu}{\min_{\|v\|=1} \sum_i v^\ast B_iv}. $ Suppose $u_0$ and $v_0$ are respectively the maximizer of the numerator and minimizer of the denominator of last expression. By assumption on submatrices of the form $M_1$, each $B_i$ is positive definite. Therefore \begin{align} \frac{\sigma_1^2(M)}{\sigma_n^2(M)} =\frac{\sum_i u_0^\ast B_iu_0}{\sum_i v_0^\ast B_iv_0} &\le\max_{i=1,\ldots,n+1}\frac{u_0^\ast B_iu_0}{v_0^\ast B_iv_0}\\ &\le\max_{i=1,\ldots,n+1}\frac{\max_{\|u\|=1} u^\ast B_iu}{\min_{\|v\|=1} v^\ast B_iv}\\ &=\max\left\{\frac{\sigma_1^2(M_1)}{\sigma_n^2(M_1)}: \ M_1 \textrm{ is an } n\times n \textrm{ submatrix of } M\right\}. \end{align} Hence the result.
-
0user1551, I am over my head with this material. My one contribution is having enough reputation points to see deleted posts on bot MSE and MO, so I was able to gather up screenshot jpegs of all the self-deleted evidence. If this is a new area of investigation, I imagine that is a good thing. Suvrit just said he had no time to look at it but it is close enough to the others to suggest the same person asking. – 2012-12-20