2
$\begingroup$

A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions are neighbors if they share a border). Instead, she calculated the row-standardized adjacency matrix and somewhat surprisingly, the entire spectrum was real.

I was wondering whether this was to be expected, or if there is something special about the particular example.

Edit: I have edited out the rest of the question, which was trying to understand the probability. The answer explains why this is always the case.

Improve this question
$\endgroup$
2
  • $\begingroup$ What's exactly a "row-standardized adjacency matrix"? Is your graph oriented? $\endgroup$
    – Federico Poloni
    Commented Jul 2, 2018 at 18:05
  • 1
    $\begingroup$ I should have been more clear. It's non-oriented, and you just divide each row of the adjacency matrix by the row sum. This breaks the symmetry, which is how complex eigenvalues can arise. $\endgroup$
    – Gabe K
    Commented Jul 2, 2018 at 18:11

1 Answer 1

Reset to default
10
$\begingroup$

If the adjacency matrix is $A,$ the "row-standardized" matrix is $DA$, where $D$ is a diagonal matrix all of whose diagonal entries are positive, so has a positive diagonal square root $D^{1/2}$. Now,

$$DA = D^{1/2} D^{1/2} A D^{1/2} D^{-1/2},$$ so your matrix is similar to

$$D^{1/2} A D^{1/2},$$ which is a symmetric matrix, and so has real spectrum.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Remark: so there is nothing strange about OP's graph like he was suggesting; that property holds for every graph. $\endgroup$
    – Federico Poloni
    Commented Jul 3, 2018 at 7:44
  • $\begingroup$ That's very interesting. An immediate consequence is that the eigenvectors are orthogonal, since $D^{1/2}$ is diagonal. $\endgroup$
    – Gabe K
    Commented Jul 3, 2018 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .