MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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