How to find eigen values of this matrix

103 Views Asked by At

How to find the eigen values of this matrix of order $(p-1)(q-1)$?

\begin{bmatrix} {(p-1)I}_{(q-1\times q-1)} &&&& (-1)_{(q-1)\times (p-1)}\\(-1)^T_{(q-1)\times (p-1)} &&&& (q-1)I_{(p-1)\times (p-1)} \end{bmatrix}

where $ (-1)_{(q-1)\times (p-1)}$ denotes the matrix of size $(q-1)\times (p-1)$ consisting of all $-1's$?

I only got $0$ as an eigen value since the row sum is $0$.

How to get the other eigen values?

Please suggest me some books which can help me s

2

There are 2 best solutions below

3
On

On the subspace spanned by $\pmatrix{1_{q-1}\cr 0_{p-1}}$ and $\pmatrix{0_{q-1}\cr 1_{p-1}}$, this acts as the matrix $$ \pmatrix{p-1 & -p+1\cr -q+1 & q-1\cr}$$ which has eigenvalues $0$ and $p+q-2$. On the orthogonal complement of that, it acts as a diagonal matrix with $p-1$ diagonal entries of $q-1$ and $q-1$ of $p-1$. Thus the eigenvalues are $0$, $p+q-2$, $p-1$ (with multiplicity $q-2$) and $q-1$ (with multiplicity $p-2$).

0
On

That matrix \begin{bmatrix} {(p-1)I}_{(q-1)\times(q-1)} & (-1)_{(q-1)\times (p-1)}\\(-1)^{\rm T}_{(q-1)\times (p-1)} & (q-1)I_{(p-1)\times (p-1)} \end{bmatrix} happens to be the Laplacian matrix of the complete bipartite graph $\boldsymbol{K_{q-1,p-1}}$.

Graph theory aside, a Laplacian matrix is a matrix such that: $1)$ has integer entries (non-negative along the diagonal; either $-1$ or $0$ elsewhere), $2)$ is symmetric, and $3)$ the row sum is zero. Just like your matrix!

The following is a well-known result for Laplacian matrices (notation is mine, though):

Let $G$ and $H$ be two graphs on $m$ and $n$ vertices, respectively. Let $L_G$, $L_H$ denote their Laplacian matrices. Let $\lambda_G$ and $\lambda_H$ denote row vectors containing the increaslingly sorted eigenvalues of $L_G$ and $L_H$, resp. Let $Q_G$, $Q_H$ denote matrices whose columns are orthonormal eigenvectors for $L_G$, $L_H$, resp., such that the $i$th column corresponds to the $i$th eigenvalue.

Note that the first entry of $\lambda_G$ is zero; without loss of generality, assume the first column of $Q_G$ to be $\sqrt{m}\,{}^{-1}\,\boldsymbol{1}_m$. (Similarly for $H$.)

Then the following matrix $$L_{G \lor H} := \begin{bmatrix} L_G +nI_m& -\boldsymbol{1}_{m\times n}\\ -\boldsymbol{1}_{n\times m} &L_H +mI_n \end{bmatrix} $$represents the Laplacian matrix of a graph on $m+n$ vertices, constructed by taking $G$ and $H$ and adding edges from all the vertices in $G$ to all the vertices in $H$. (Such operation is tipycally named the joint union of $\boldsymbol{G}$ and $\boldsymbol{H}$.)

Let $\hat \lambda_G$ denote the effect of suppressing the first entry of $\lambda_G$, and let $\hat Q_G$ denote the effect of supressing the first column of $Q_G$; similarly for $H$. Then the columns of the following matrix $$\begin{bmatrix} \frac{1}{\sqrt{m+n}}\,\boldsymbol{1}_m& \hat Q_G& \boldsymbol{0}_{m\times(n-1)}& -\sqrt{\frac{n}{m(m+n)}}\,\boldsymbol{1}_m\\ \frac{1}{\sqrt{m+n}}\,\boldsymbol{1}_n& \boldsymbol{0}_{n\times(m-1)}& \hat Q_H& \sqrt{\frac{m}{n(m+n)}}\,\boldsymbol{1}_n\\ \end{bmatrix}$$ are orthonormal eigenvectors of $L_{G\lor H}$ corresponding to unsorted eigenvalues $$\begin{bmatrix} 0& \hat\lambda_G +n\,\boldsymbol{1}^{\rm T}_{m-1}& m\,\boldsymbol{1}^{\rm T}_{n-1} +\hat\lambda_H& m+n \end{bmatrix}.$$

For your specific matrix (which I rewrote a little) \begin{bmatrix} (p-1) I_{q-1}& -\boldsymbol{1}_{(q-1)\times(p-1)}\\ -\boldsymbol{1}^{\rm T}_{(q-1)\times (p-1)}& (q-1) I_{p-1} \end{bmatrix} It is of the form $L_{G\lor H}$ if and only if $L_G$ is a $(q-1)\times(q-1)$ zero matrix (which has eigenvalue $0$ with multiplicity $q-1$) and if $L_H$ is a $(p-1)\times(p-1)$ zero matrix (eigenvalue $0$ with multiplicity $p-1$). Plugging $m \gets q-1$, $\hat\lambda_G \gets \boldsymbol{0}^{\rm T}_{q-2}$, $n \gets p-1$ and $\hat\lambda_H \gets \boldsymbol{0}^{\rm T}_{p-2}$ for the unsorted eigenvalues of $L_{G\lor H}$ gives $$\begin{bmatrix} 0& (p-1)\,\boldsymbol{1}^{\rm T}_{q-2}& (q-1)\,\boldsymbol{1}^{\rm T}_{p-2}& q+p-2 \end{bmatrix}.$$ That is, your matrix has eigenvalues $0$ with multiplicity $1$, $p-1$ with multiplicity $q-2$, $q-1$ with multiplicity $p-2$, and $q+p-2$ with multiplicity $1$.

Some sources I checked on the subject a while ago:

  • Merris, R. ($1994$): Laplacian Matrices of Graphs. A survey. Linear Algebra and its Applications, Num. $197$, pags. $143$-$176$.
  • Merris, R. ($1998$): Laplacian graph eigenvectors. A survey. Linear Algebra and its Applications, Num. $278$, pags. $221$-$236$.
  • Molitierno, J. J. ($2012$): Applications of Combinatorial Matrix Theory for Laplacian Matrices of Graphs. Discrete Mathematics and Its Applications. CRC Press.