How to find eigen values of difference of two matrices

Question

Let $K_{p,q}$ denote the complete bipartite graph .

I want to find the eigen values of $L(K_{p,q})$ where $L(G)$ denotes the Laplacian Matrix of a graph $G$.

$L(G)=a_{ij}=$

$$\begin{array}{ccc} d_i &\mbox{i= j}\\ -1 &\mbox{$i\sim j$}\\ 0 &\mbox{otherwise} \end{array} $$

My try:

I know that $L(G)=D(G)-A(G)$ where $D(G)$ denotes the degree matrix of $G$. I have found out that the eigen values of $A(G)$ are $0$ of multiplicity $p+q-2$ and $,\sqrt{pq},-\sqrt{pq}$ each of multiplicity $1$ and the eigen values of $D(G)$ are $p$ of multiplicity $q$ and $q$ of multiplicity $p$.

But I am not getting how to get the eigen values of $L(G)$ from here?

Please give some hints.

Answer 1

Let $I_p$ and $I_q$ be the identity matrices of orders $p$ and $q$ respectively, and let $J$ be the all-ones matrix of order $p \times q$. Then the Laplacian matrix $L$ of the complete bipartite graph $K_{p,q}$ is \begin{equation*} L = \left[\begin{array}{c|c} qI_p & -J\\ \hline -J^T & pI_q \end{array}\right]. \end{equation*}

Then, to find the characteristic polynomial, \begin{equation*} xI - L = \left[\begin{array}{c|c} (x-q)I_p & J\\ \hline J^T & (x - p)I_q \end{array}\right] = \left[\begin{array}{c|c} A & B\\ \hline C & D \end{array}\right]. \end{equation*}

Now we observe the following:

1. If we substitute $x = p$, the matrix $D$ becomes the zero matrix, so the lower block made up of $C = J^T$ and $D$ consists of $q$ identical rows. Assuming $p \ne q$ (for now), $A = (p - q)I$ has full rank ($ = p$), and therefore, so does upper block $[A\ B]$. Therefore, $pI - L$ is a matrix of rank $p + 1$, and thus, with nullity $q - 1$ (since its order is $p + q$). This implies that $x = p$ is an eigenvalue of $L$ with multiplicity $q - 1$ (assuming $p \ne q$).
2. An exactly similar argument shows us that $q$ is an eigenvalue of $L$ with multiplicity $p - 1$, again assuming $p \ne q$.
3. We know that zero is always an eigenvalue of $L$, with multiplicity $1$ if the graph is connected, which is so in our case. Alternatively, observe that the all-ones vector $\mathbf 1$ is an eigenvector of $L$ for eigenvalue zero (since the row sum is zero for each row).
4. Let $v = \begin{bmatrix}\mathbf q1_p\\ -p\mathbf 1_q\end{bmatrix}$ denote the matrix with first $p$ entries equal to $q$ and remaining $q$ entries equal to $-p$. Then observe that $Lv = (p + q)v$. Thus, $p + q$ is an eigenvalue of $L$, necessarily with multiplicity $1$ (since we have already found $p + q - 1$ other eigenvalues).
5. Finally, consider the special case $p = q$. Then, $x = p$ makes both blocks $A$ and $D$ null matrices, so \begin{equation*} pI - L = \left[\begin{array}{c|c} \mathbf 0 & -J\\ \hline -J^T & \mathbf 0 \end{array}\right]. \end{equation*} This matrix obviously has rank $2$, and therefore nullity $p + q - 2 = 2p - 2$. Thus, $L$ has an eigenvalue $p$ with multiplicity $2(p - 1)$. The arguments (3) and (4) above still hold, so the other eigenvalues are zero and $2p$ with multiplicites $1$ each.

Therefore, the spectrum of $L$ is, for $p \ne q$, \begin{pmatrix} 0 & p & q & p + q\\ 1 & q - 1 & p - 1 & 1 \end{pmatrix} and for $p = q$, \begin{pmatrix} 0 & p & 2p\\ 1 & 2(p - 1) & 1 \end{pmatrix} where the first row values are the eigenvalues and the second row values are the corresponding multiplicities.