# Principal eigenvector of non-negative symmetric block matrix is approximated by a linear combination of the principal eigenvectors of the blocks

Let $$M \in \mathbb{R}^{n \times n} = \begin{bmatrix} A & B \\ B^T & C \end{bmatrix}$$ for some nonnegative $$A \in \mathbb{R}^{k \times k}, B \in \mathbb{R}^{k \times n-k}, C \in \mathbb{R}^{n-k \times n-k}$$ with $$A$$ and $$B$$ symmetric have maximum eigenvalue $$\lambda_M$$ and corresponding eigenvector $$e= \begin{bmatrix} e_1 \\ e_2 \end{bmatrix}$$ for some $$e_1 \in \mathbb{R}^k,e_2 \in \mathbb{R}^{n-k}$$. We can write $$M=\begin{bmatrix}A & \mathbf{0} \\ \mathbf{0} & \mathbf{0}\end{bmatrix} + \begin{bmatrix}\mathbf{0} & B \\ B^T & \mathbf{0}\end{bmatrix} + \begin{bmatrix}\mathbf{0} & \mathbf{0} \\ \mathbf{0} & C\end{bmatrix}$$, and let $$\lambda_A, \lambda_B, \lambda_C$$ be the maximum eigenvalues of these matrices respectively, with corresponding eigenvectors $$\begin{bmatrix} a \\ \mathbf{0}\end{bmatrix}$$, $$\begin{bmatrix} b_1 \\ b_2\end{bmatrix}$$, $$\begin{bmatrix} \mathbf{0} \\ c\end{bmatrix}$$, and WLOG we can assume that all of these eigenvectors are nonnegative.

I know in general there is not necessarily any relation between the eigenvalues and eigenvectors of $$M$$ and those of its component matrices, but I have observed empirically that $$\widetilde{e}=\lambda_A \begin{bmatrix} a \\ \mathbf{0}\end{bmatrix}+ \lambda_B \begin{bmatrix} b_1 \\ b_2\end{bmatrix}+ \lambda_C \begin{bmatrix} \mathbf{0} \\ c \end{bmatrix}$$ is always quite close to the direction of $$e$$, usually off by at most a few degrees.

In particular, I'm interested in adjacency matrices, and I've observed that $$\widetilde{e}$$ gets closer to $$e$$ the denser the adjacency matrix is, with equality if it is the adjacency matrix of a complete graph. This relation does not hold if I remove the assumptions of nonnegativity and symmetry, or if it is the adjacency matrix of a disconnected graph.

I'm trying to find a way to quantify the relationship between $$e$$ and $$\widetilde{e}$$ and hopefully bound the difference between them. I've been working with the Rayleigh quotient trying to take advantage of the fact that $$\frac{e^TMe}{e^Te} \geq \frac{\widetilde{e}^TM\widetilde{e}}{\widetilde{e}^T\widetilde{e}}$$ as well as trying to find geometric relationships between the vectors, but I'm not sure how to move forward. It seems that $$e$$ is almost in the span of $$\begin{bmatrix} a & b_1 & \mathbf{0} \\ \mathbf{0} & b_2 & c \end{bmatrix}$$; $$\widetilde{e}$$ is at least as close to $$e$$ as the least-squares solution to $$\begin{bmatrix} a & b_1 & \mathbf{0} \\ \mathbf{0} & b_2 & c \end{bmatrix}x=e$$ so it must be optimal in some respect, but I don't know how to quantify any of these intuitions.

Thanks in advance, sorry if my presentation is unclear or if this should be asked on math.stackexchange 🙃

• What does it mean for a rectangular matrix to be symmetric (or non-negative)? – lcv Dec 21 '18 at 1:44
• M, A and C are square and symmetric. B isn't necessarily square or symmetric but the block matrix containing just B, its transpose and zeros is. By non-negative I mean that all of the entries are non-negative. – Ross Griebenow Dec 21 '18 at 18:28