3
$\begingroup$

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 🙃

$\endgroup$
2
  • $\begingroup$ What does it mean for a rectangular matrix to be symmetric (or non-negative)? $\endgroup$
    – lcv
    Dec 21, 2018 at 1:44
  • $\begingroup$ 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. $\endgroup$ Dec 21, 2018 at 18:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.