Is there a lower bound for the determinant or minimum eigenvalue of the following $d$ by $d$ matrix in terms of $d$?

$$\Gamma=\left( {\begin{array}{cc} I & B \\ B^{*} & I \\ \end{array} } \right)$$ Where $I$ is the identity matrix and the the moduli of entries of $B$ and those of its conjugate $B^{*}$ are all equal to $\frac{1}{\sqrt{d}}$. Also the blocks are all $\frac{d}{2}$by$\frac{d}{2}$. $\Gamma$ is a Gram matrix and further assume that the rows and columns are linearly independent. Hence we know that the lower bound is larger than zero but can we say anything more?

For simplicity we can assume the field of the matrix is real. Hence the entries of the off-diagonal blocks ($B$ and $B^{T}$) are $\pm\frac{1}{\sqrt{d}}$.

I appreciate any input very much!


Let me write $$\Gamma_\mu = \begin{pmatrix} \mu I & B \\ B^* & \mu I \end{pmatrix} ,$$ so that your $\Gamma = \Gamma_1$. The eigenvalues of $\Gamma_0$ are easy to analyze given the equivalent reformulation \begin{equation} \begin{pmatrix} 0 & B \\ B^* & 0 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \lambda \begin{pmatrix} x \\ y \end{pmatrix} \iff \begin{cases} B B^* x &= \lambda^2 x \\ y &= \frac{1}{\lambda} B^* x \end{cases} . \end{equation} You can see that the eigenvalues of $\Gamma_0$ are precisely given by $\lambda^\pm_i(\Gamma_0) = \pm \sigma_i(B)$, where $\sigma_i(B)$ are the singular values of $B$ (equivalently, positive square roots of the eigenvalues of $B B^*$). Thus, $\lambda^\pm_i(\Gamma_\mu) = \mu \pm \sigma_i(B)$. So, finally, $$ \min_i \lambda^\pm_i(\Gamma_1) = 1 - \max_i \sigma_i(B) . $$

I guess next you would need to have a more precise bound on $\sigma_i(B)$, for which I don't have a good idea at the moment.

  • $\begingroup$ Thank you for your answer. That is right the problem comes down to upper-bounding the maximum singular value of $B$. Another way of looking at it is to consider the equation for determinant of block matrices which in our case would be $$|\Gamma|=|I-B^{*}B|$$ which yields the same results. Now for upper-bounding $\sigma_{\max}(B}$, can we use the entry-wise 4-norm of $B$ in anyway? This norm is $$\frac{1}{\sqrt{2}}$$. What restrictions on $B$ would make this norm useful? An obvious restriction is when the rows of $B$ are orthogonal which would yield $$|\Gamma|=(\frac{1}{2})^{\frac{d}{2}$$. $\endgroup$ – Jay Jun 19 '15 at 19:57
  • $\begingroup$ But this restriction is too trivial. What if $B$ is symmetric? can we use the the 4-norm? @Igor Khavkine $\endgroup$ – Jay Jun 19 '15 at 20:01
  • $\begingroup$ Also, $\frac{1}{\sqrt{d}}B$ is a (1,-1) matrix (assuming the field is real). Another thing we can consider is that it is sub-Hadamard matrix. $\endgroup$ – Jay Jun 19 '15 at 20:05
  • $\begingroup$ Another point that I would like to ask is, according to what you just explained, eigenvalues of $\Gamma_{1}$ are symmetric with respect to one in the sense that:$$\lambda_{i}^{\pm}(\Gamma_{1})=1\pm\sigma_{i}(B)$$, does that mean lower-bounding the minimum eigenvalue of $\Gamma_{1}$ can be done by upper-bounding its maximum eigenvalue? $\endgroup$ – Jay Jun 20 '15 at 16:41
  • $\begingroup$ The eigenvalues $\lambda_i^\pm(\Gamma_0) = \pm \sigma_i(B)$ are indeed symmetric about $0$, so the answer to your question is clearly yes. The eigenvalues of $\Gamma_\mu$ are just jointly shifted by $\mu$ on the real axis. $\endgroup$ – Igor Khavkine Jun 20 '15 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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