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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.