How Do Eigenvalues of Block Matrices Relate to Their Sub-Matrices and Graphs?

[Adel Makram]

If there is matrix that is formed by blocks of 2 x 2 matrices, what will be the relation between the eigen values and vectors of that matrix and the eigen values and vectors of the sub-matrices?

 

[hilbert2]

If the matrices $\mathbf{A}$ and $\mathbf{B}$ are 2x2 matrices, $\mathbf{C} = \begin{bmatrix}\mathbf{A}\hspace{10pt}0\\0\hspace{10pt}\mathbf{B}\end{bmatrix}$ is a block matrix formed from them, and $\mathbf{v}=\begin{bmatrix}a\\b\\c\\d\end{bmatrix}$ is an eigenvector of $\mathbf{C}$ with eigenvalue $c$, then $c$ must also be an eigenvalue of both $\mathbf{A}$ and $\mathbf{B}$, or at least an eigenvalue of one of them in the case where $a=b=0$ or $c=d=0$.

 

[Adel Makram]

If the matrices $\mathbf{A}$ and $\mathbf{B}$ are 2x2 matrices, $\mathbf{C} = \begin{bmatrix}\mathbf{A}\hspace{10pt}0\\0\hspace{10pt}\mathbf{B}\end{bmatrix}$ is a block matrix formed from them, and $\mathbf{v}=\begin{bmatrix}a\\b\\c\\d\end{bmatrix}$ is an eigenvector of $\mathbf{C}$ with eigenvalue $c$, then $c$ must also be an eigenvalue of both $\mathbf{A}$ and $\mathbf{B}$, or at least an eigenvalue of one of them in the case where $a=b=0$ or $c=d=0$.

This is clear if C is a diagonal matrix with entries are real numbers, in such case, the eigen vectors of C is $(1,0,0...0)^T$, ...$(0,0,0...1)^T$ and the eigen values are the numbers themselves. The eigen vectors and eigen values of each block will follow the same pattern.
What if C has diagonals of 0 and off-diagonal of real numbers?

 

[hilbert2]

It also holds in the case $\mathbf{C}=\begin{bmatrix}1 & 2 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 0 & 0 & 2 & 3 \\ 0 & 0 & 3 & 2\end{bmatrix}$ or some other block-diagonal matrix.

An eigenvector of $\begin{bmatrix}\mathbf{A} & 0 \\ 0 & \mathbf{B}\end{bmatrix}$ is also an eigenvector of $\begin{bmatrix}0 & \mathbf{A} \\ \mathbf{B} & 0\end{bmatrix}$, if it is symmetric or antisymmetric in the interchange of the upper and lower two elements:

$\begin{bmatrix}a \\ b \\ c \\ d\end{bmatrix} = \pm\begin{bmatrix}c \\ d \\ a \\ b\end{bmatrix}$.

 

[Adel Makram]

It also holds in the case $\mathbf{C}=\begin{bmatrix}1 & 2 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 0 & 0 & 2 & 3 \\ 0 & 0 & 3 & 2\end{bmatrix}$ or some other block-diagonal matrix.

An eigenvector of $\begin{bmatrix}\mathbf{A} & 0 \\ 0 & \mathbf{B}\end{bmatrix}$ is also an eigenvector of $\begin{bmatrix}0 & \mathbf{A} \\ \mathbf{B} & 0\end{bmatrix}$, if it is symmetric or antisymmetric in the interchange of the upper and lower two elements:

$\begin{bmatrix}a \\ b \\ c \\ d\end{bmatrix} = \pm\begin{bmatrix}c \\ d \\ a \\ b\end{bmatrix}$.

I used online matrix calculator and I found no obvious correlation between the eigen vectors or eigen values of the $\begin{bmatrix}\mathbf{A} & 0 \\ 0 & \mathbf{B}\end{bmatrix}$ and $\begin{bmatrix}0 & \mathbf{A} \\ \mathbf{B} & 0\end{bmatrix}$. There is of course obvious similarity as described above in the first matrix and its two blocks. However, this similarity is not there if it is antisymmetrical one. Also, antisymmetrical matrix should have the transpose equal to its negative by definition, so the second matrix should be called something else.

 

[hilbert2]

Try to calculate what happens when

$\mathbf{A}=\begin{bmatrix}6 & 3 \\ 3 & 6\end{bmatrix}$
$\mathbf{B}=\begin{bmatrix}1 & -2 \\ -2 & 1\end{bmatrix}$
$\mathbf{C}=\begin{bmatrix}6 & 3 & 0 & 0 \\ 3 & 6 & 0 & 0 \\ 0 & 0 & 1 & -2 \\ 0 & 0 & -2 & 1\end{bmatrix}$
$\mathbf{D}=\begin{bmatrix}0 & 0 & 6 & 3 \\ 0 & 0 & 3 & 6 \\ 1 & -2 & 0 & 0\\ -2 & 1 & 0 & 0\end{bmatrix}$.

The vector $\begin{bmatrix}-1 \\ 1 \\ -1 \\ 1\end{bmatrix}$ is an eigenvector of both $\mathbf{C}$ and $\mathbf{D}$ with eigenvalue $3$. Note that if two eigenvectors are degenerate (have the same eigenvalue), then their sum is also an eigenvector with same eigenvalue.

 

[Adel Makram]

But the matrices in the last example have rows and columns which are linear combination of each other. What if we have a matrix with random entries like the one in your post #4. Again, will be any relationship between the eigen values of the matrix and its blocks matrices?

 

[StoneTemplePython]

Again, will be any relationship between the eigen values of the matrix and its blocks matrices?

I'll try to add a bit to this by ignoring eigenvectors and just focusing on eigenvalues. I assume that $\mathbf A$ and $\mathbf B$ are in both $n$ x $n$ (i.e. $n\geq 2$ ) and in reals.

E.g. consider

$\mathbf X = \begin{bmatrix}\mathbf{A} & \mathbf 0 \\ \mathbf 0 & \mathbf{B}\end{bmatrix}$

notice that $det\big(\mathbf X\big) =det\big(\mathbf A\big)det\big(\mathbf B\big)$

(for a proof and a lot more info on blocked multiplication of matrices, look at page 108 of https://math.byu.edu/~klkuttle/Linearalgebra.pdf )

and

$\mathbf Y = \begin{bmatrix}\mathbf 0 &\mathbf{A} \\ \mathbf{B} &\mathbf 0\end{bmatrix}$

$\big \vert det\big(\mathbf Y\big)\big \vert =\big \vert det \big(\mathbf A\big)det\big(\mathbf B\big)\big \vert$

(I put an absolute value sign in there as I want to ignore the sign implications related to number of column swaps needed to "convert" $\mathbf Y$ to $\mathbf X$).

sometimes its useful to just multiply these things out.

$\mathbf X^2 = \begin{bmatrix}\mathbf{A}^2 & \mathbf 0 \\ \mathbf 0 & \mathbf{B}^2\end{bmatrix}$

$\mathbf Y^2 = \begin{bmatrix}\mathbf{AB} & \mathbf 0 \\ \mathbf 0 & \mathbf{BA}\end{bmatrix}$

and as we'd expect $det\big(\mathbf X^2\big) = det\big(\mathbf Y^2\big)$

You could say that the eigenvalues of $\mathbf X$ are a function of the eigenvalues of $\mathbf A$ and the eigenvalues of $\mathbf B$. However the eigenvalues of $\mathbf Y$ are in some sense a function of the eigenvalues of $\big(\mathbf {AB}\big)$ -- which of course are the same as those for $\big(\mathbf {BA}\big)$

- - - - - - -
We can say lot more if our submatrices have special structure. E.g. suppose $\mathbf A$ and $\mathbf B$ are both real symmetric. In this case we can say

$\mathbf X^2 = \mathbf X^T \mathbf X = \begin{bmatrix}\mathbf{A}^T \mathbf A & \mathbf 0 \\ \mathbf 0 & \mathbf{B}^T\mathbf B \end{bmatrix}$

$\mathbf Y^T \mathbf Y = \begin{bmatrix}\mathbf{B}^T \mathbf B & \mathbf 0 \\ \mathbf 0 & \mathbf{A}^T\mathbf A \end{bmatrix}$

but this tells us that the sum of the eigenvalues of $\mathbf X^2$ is larger than the sum of those of $\mathbf Y^2$, because $trace\big(\mathbf X^2\big) = trace\big(\mathbf X^T\mathbf X\big) = trace\big(\mathbf Y^T\mathbf Y\big) \geq trace\big(\mathbf Y^2\big)$

(why?... also note if $\mathbf A \neq \mathbf B$ then the inequality is strict.)

It's also worth pointing out that we can be certain that $\mathbf X$ only has real eigenvalues, whereas $\mathbf Y$ may have complex eigenvalues coming in conjugate pairs. (Note: this is still true if $\mathbf A$ and $\mathbf B$ are both Hermitian, with scalars in $\mathbb C$.)

So $\mathbf X$ and $\mathbf Y$ are linked via their determinants, but the actual structure of their eigenvalues is going to be rather different.

- - - -
Stepping back a bit and thinking more generally, it's also worth looking at the block upper triangular matrix $\mathbf T$

$\mathbf T = \begin{bmatrix}\mathbf{A} & \mathbf * \\ \mathbf 0 & \mathbf{B}\end{bmatrix}$

where $\mathbf *$ indicates entries we are not concerned with.

This matrix has its eigenvalues specified entirely by those of $\mathbf A$ and $\mathbf B$. There are severals ways to verify this. Kuttler shows the typical way. My preferred approach is to just multiply it out and note that for any natural number $k = 1, 2, 3,...$

$\mathbf T^k = \begin{bmatrix}\mathbf{A}^k & \mathbf * \\ \mathbf 0 & \mathbf{B}^k\end{bmatrix}$

hence
$trace\big(\mathbf T^k\big) = trace\big(\mathbf{A}^k + \mathbf{B}^k\big) = trace\big(\mathbf{A}^k\big) + trace\big(\mathbf{B}^k\big)$

for all natural numbers $k$

 

[Adel Makram]

You could say that the eigenvalues of XX\mathbf X are a function of the eigenvalues of AA\mathbf A and the eigenvalues of BB\mathbf B. However the eigenvalues of YY\mathbf Y are in some sense a function of the eigenvalues of (AB)(AB)\big(\mathbf {AB}\big) -- which of course are the same as those for (BA)(BA)\big(\mathbf {BA}\big)

Thank you for comprehensive analysis. But should be any closed form for that function of the eigen value of A and the eigenvalues of B?
For example, suppose X represents the transitional probability in Markov chain process, will I be able to represent it, using certain transformation, by a Markov transitions process at the level of 2 x 2 submatrices? Of course in that case the sum of probabilities in each row=1 because there will be only 2 entries in each rows and each columns so the probability completion condition is satisfied.

 

[StoneTemplePython]

Thank you for comprehensive analysis. But should be any closed form for that function of the eigen value of A and the eigenvalues of B?
For example, suppose X represents the transitional probability in Markov chain process, will I be able to represent it, using certain transformation, by a Markov transitions process at the level of 2 x 2 submatrices? Of course in that case the sum of probabilities in each row=1 because there will be only 2 entries in each rows and each columns so the probability completion condition is satisfied.

You may need to re-ask this as I'm not totally sure what you're getting at. In your example, if you have a markov chain with 2 distinct non-communicating clasess of nodes, then you may be able to use $\mathbf X$.

In general looking at the graph-theoretic implications of having blocked matrices with special structure (e.g. $\mathbf T$ would have $\mathbf A$ and $\mathbf B$ as recurrent classes and $*$ as transient states in a Markov chain) can be quite enlightening.

 

[Adel Makram]

You may need to re-ask this as I'm not totally sure what you're getting at. In your example, if you have a markov chain with 2 distinct non-communicating clasess of nodes, then you may be able to use $\mathbf X$.

In general looking at the graph-theoretic implications of having blocked matrices with special structure (e.g. $\mathbf T$ would have $\mathbf A$ and $\mathbf B$ as recurrent classes and $*$ as transient states in a Markov chain) can be quite enlightening.

This is close to what I am thinking in. If X is an nxn matrix in certain vector space with entries representing some coefficients, it would be wonderful if we can reduce this representation to some form of 2x2 blocks of its states even if it is in some other space. For example, In Markov case, if X is the transitional probability matrix of 10 states representing some class, or space, of variables, will it be possible to transform it into block of 2x2 matrices of many 2 states in some other transformed space. In general, if we have a graph of many branches from any node in it, will it possible to transform it into another graph with only two nodal branching system in which there are just 2 branches from any node?
If this possible, then there could be potential for applying it in quantum mechanics. Just an example, any matrix representing a quantum observable with many states can be potentially reduced to blocks of 2x2 matrices that represents other observable with only two states.
I hope my wording was clear in this post but to be honest still the idea is not so clear in my mind. The objective is to reduce any matrix to blocks of 2x2 sub matrices by a sort of transformation.

 

[StoneTemplePython]

if we have a graph of many branches from any node in it, will it possible to transform it into another graph with only two nodal branching system in which there are just 2 branches from any node?

I'm concerned this thread is wandering very far off course. The short, almost tautological, answer to your question is: if your original graph is isomorphic to this two nodal branching system, then yes. Otherwise, not so much.

- - -
Note: you can always take a $2m$ x $2m$ matrix with scalar entries and equivalently represent it as a $m$ x $m$ matrix having 2x2 blocks. (In fact, this is one way of interpreting quarternion matrices.) But the arc of this entire thread is not just arbitrarily blocking matrices but looking for special /useful structure in the blocks. There is no general purposes process for this and the structure may or may not exist. Note: there isn't even a very good general purpose algorithm for graph isomorphism yet -- graph isomorphism problems are viewed as being a bit harder than prime factoring but easier than NP Complete (though we aren't sure). But this is pretty far off course.