When we study the structure of simple graphs with a lot of $1$ or $-1$ as its adjacency eigenvalues, the rank of its adjacency matrix is very important. The reason is, in these case, we can study the matrix $A+I$ and $A-I$, where $A$ is the adjacency matrix of graph $G$.

Let $A$ be a symmetric $n\times n$ matrix such that $A+I$ has rank $k$. It is obvious to see that, $A$ has $k$ eigenvalues $-1$. Since $A$ is symmetric, we can write

\begin{equation*} A+I= \begin{bmatrix} A_1& B \newline B^T& A_2 \end{bmatrix} , \end{equation*}

where $A_1$ is a $k\times k$ matrix, $B$ is $k\times (n-k)$ matrix, $B^T$ is the transpose of $B$ and $A_2$ is $(n-k)\times (n-k)$ matrix. It is easy to see that $A_1$ is nonsingular.

My question is:

1) In general, is it true that $A_2=B^TA_1^{-1}B$, and if it is true, how we can prove it? We can see that $rank(A+I)=rank(A_1)$. May be it can help for proof as a strategy.

2) Would you please give me some references for these types of relations in matrices?

For rank$(A_1)=2$ or rank$(A_1)=3$, Professor Doob and Professor Haemers showed that, the structure of $A$ are determined, equivalently, the graphs with $n$ vertices and $n-2$ or $n-3$ eigenvalues $-1$ are determined by their adjacency spectrum. The answer for $n-4$ eigenvalues equal to $-1$ is negative. My another question is:

For which integer $n-k$, where $4\leq k\leq n$, the answer is known? I mean, if the multiplicity of $-1$ for graph $G$ with $n$ vertices be $n-k$, what are the known results about cospectral mate?

Professor Doob and Haemers, gave and example for $n-4$. I found some examples in other cases. I think these examples are important. Am I thinking truly?

I will appreciate any helpful answer and guidance.


It may take some reordering of the rows (and correspondingly the columns) to make $A_1$ nonsingular.

If it is, consider $$( A+I) \pmatrix{A_1^{-1} & -A_1^{-1} B\cr 0 & I\cr} = \pmatrix{I & 0\cr B^T A_1^{-1} & A_2 - B^T A_1^{-1} B\cr}$$

If this has rank $k$, the lower right block must be $0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.