Show that the largest eigenvalue of $A$ lies in the given interval

Question

Show that if the given matrix $A$ is positive semi-definite then the largest eigen value of $A$ lies in the interval $(6,7)$.

$$A=\begin{bmatrix} 5&1&1&1&1&1\\ 1&2&1&0&0&0\\ 1&1&2&0&0&0\\ 1&0&0&1&0&0\\ 1&0&0&0&1&0\\ 1&0&0&0&0&1 \end{bmatrix}$$

My try:

Since the matrix is given to be positive semidefinite so the spectral radius $\rho(A)$ must be an eigen value of $A$.

Also $\rho (A)=\max_{||x||=1}x^TAx$

I considered the vector $x=(1,0,0,0,0,0)$ then $\rho(A)\ge 5$

So I tried various $x$ such that $||x||=1$ but I find largest lower bound to be $5$.

Is there any way I can show that $\rho\ge 6$

Answer 1

first things, it is positive definite, by Sylvester's Law of Inertia

The law can also be stated as follows: two symmetric square matrices of the same size have the same number of positive, negative and zero eigenvalues if and only if they are congruent $ S ′ = A S A^T \; , \; $ with $A$ nonsingular

$$ Q^T D Q = H $$ $$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ \frac{ 1 }{ 5 } & 1 & 0 & 0 & 0 & 0 \\ \frac{ 1 }{ 5 } & \frac{ 4 }{ 9 } & 1 & 0 & 0 & 0 \\ \frac{ 1 }{ 5 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 13 } & 1 & 0 & 0 \\ \frac{ 1 }{ 5 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 13 } & - \frac{ 3 }{ 10 } & 1 & 0 \\ \frac{ 1 }{ 5 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 13 } & - \frac{ 3 }{ 10 } & - \frac{ 3 }{ 7 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 5 & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{ 9 }{ 5 } & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 13 }{ 9 } & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 10 }{ 13 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 7 }{ 10 } & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{ 4 }{ 7 } \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & \frac{ 1 }{ 5 } & \frac{ 1 }{ 5 } & \frac{ 1 }{ 5 } & \frac{ 1 }{ 5 } & \frac{ 1 }{ 5 } \\ 0 & 1 & \frac{ 4 }{ 9 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 9 } \\ 0 & 0 & 1 & - \frac{ 1 }{ 13 } & - \frac{ 1 }{ 13 } & - \frac{ 1 }{ 13 } \\ 0 & 0 & 0 & 1 & - \frac{ 3 }{ 10 } & - \frac{ 3 }{ 10 } \\ 0 & 0 & 0 & 0 & 1 & - \frac{ 3 }{ 7 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 5 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 1 & 1 & 2 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$

Next, if $7I - H$ is also positive definite, but $6I - H$ indefinite, the largest eigenvalue lies between 6 and 7....

$$ Q_7^T D_7 Q_7 = 7I-H $$ $$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ - \frac{ 1 }{ 2 } & 1 & 0 & 0 & 0 & 0 \\ - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 3 } & 1 & 0 & 0 & 0 \\ - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 6 } & 1 & 0 & 0 \\ - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 6 } & - \frac{ 1 }{ 8 } & 1 & 0 \\ - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 6 } & - \frac{ 1 }{ 8 } & - \frac{ 1 }{ 7 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & \frac{ 9 }{ 2 } & 0 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 16 }{ 3 } & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{ 21 }{ 4 } & 0 \\ 0 & 0 & 0 & 0 & 0 & \frac{ 36 }{ 7 } \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 2 } & - \frac{ 1 }{ 2 } \\ 0 & 1 & - \frac{ 1 }{ 3 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 9 } & - \frac{ 1 }{ 9 } \\ 0 & 0 & 1 & - \frac{ 1 }{ 6 } & - \frac{ 1 }{ 6 } & - \frac{ 1 }{ 6 } \\ 0 & 0 & 0 & 1 & - \frac{ 1 }{ 8 } & - \frac{ 1 }{ 8 } \\ 0 & 0 & 0 & 0 & 1 & - \frac{ 1 }{ 7 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 2 & - 1 & - 1 & - 1 & - 1 & - 1 \\ - 1 & 5 & - 1 & 0 & 0 & 0 \\ - 1 & - 1 & 5 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 6 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 6 & 0 \\ - 1 & 0 & 0 & 0 & 0 & 6 \\ \end{array} \right) $$

$$ Q_6^T D_6 Q_6 = 6I - H $$ $$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 & 0 & 0 \\ - 1 & - \frac{ 2 }{ 3 } & 1 & 0 & 0 & 0 \\ - 1 & - \frac{ 1 }{ 3 } & - 1 & 1 & 0 & 0 \\ - 1 & - \frac{ 1 }{ 3 } & - 1 & - \frac{ 3 }{ 2 } & 1 & 0 \\ - 1 & - \frac{ 1 }{ 3 } & - 1 & - \frac{ 3 }{ 2 } & 3 & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{ 5 }{ 3 } & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & - \frac{ 5 }{ 2 } & 0 \\ 0 & 0 & 0 & 0 & 0 & 20 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & - 1 & - 1 & - 1 & - 1 & - 1 \\ 0 & 1 & - \frac{ 2 }{ 3 } & - \frac{ 1 }{ 3 } & - \frac{ 1 }{ 3 } & - \frac{ 1 }{ 3 } \\ 0 & 0 & 1 & - 1 & - 1 & - 1 \\ 0 & 0 & 0 & 1 & - \frac{ 3 }{ 2 } & - \frac{ 3 }{ 2 } \\ 0 & 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 1 & - 1 & - 1 & - 1 & - 1 & - 1 \\ - 1 & 4 & - 1 & 0 & 0 & 0 \\ - 1 & - 1 & 4 & 0 & 0 & 0 \\ - 1 & 0 & 0 & 5 & 0 & 0 \\ - 1 & 0 & 0 & 0 & 5 & 0 \\ - 1 & 0 & 0 & 0 & 0 & 5 \\ \end{array} \right) $$

Answer 2

There exist $2\times 2$ orthogonal matrix $Q_2$ and $3\times 3$ orthogonal matrix $Q_3$ such that $$Q_2\begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix}\sqrt{2}\\0\end{bmatrix}\quad\text{and}\quad Q_3\begin{bmatrix}1\\1\\1\end{bmatrix}=\begin{bmatrix}\sqrt{3}\\0\\0\end{bmatrix}\,,$$ e.g. Householder reflections. Define $6\times6$ orthogonal block diagonal matrix $Q$ with $Q=\operatorname{diag}(1,Q_2,Q_3)$ and note that matrix $A$ is similar to the matrix $$QAQ^T=\begin{bmatrix}5&\sqrt{2}&0&\sqrt{3}&0&0\\\sqrt{2}&3&0&0&0&0\\0&0&1&0&0&0\\\sqrt{3}&0&0&1&0&0\\0&0&0&0&1&0\\0&0&0&0&0&1\end{bmatrix}\,.$$

Now we know that eigenvalues of $A$ different from $1$ must be eigenvalues of the matrix $B$ defined as $$B=\begin{bmatrix}5&\sqrt{2}&\sqrt{3}\\\sqrt{2}&3&0\\\sqrt{3}&0&1\end{bmatrix}\,.$$ Also, $\rho(A)=\max\{1,\rho(B)\}\,.$

Characteristic polynomial of matrix $B$ is $$k(\lambda) = \lambda^3-9\lambda^2+18\lambda-4\,.$$ Its derivative is a quadratic polynomial whose zeros are $3\pm\sqrt{3}$. From here we conclude that $k'(\lambda)>0$ for $\lambda\in(3+\sqrt{3},+\infty)$. This means that $k(\lambda)$ is strictly increasing on that interval and has at most one zero in it. Since $k(6)=-4<0$ and $k(7)=24>0$, we know that zero is actualy in $(6,7)$. This shows that the largest eigenvalue of $B$, $\rho(B)$, satisfies $6<\rho(B)<7$, from where $6<\rho(A)<7$ follows.