We know from the Perron-Frobenius theorem that for a non-negative matrix, $A$, (symmetric or asymmetric) the largest eigenvalue is simple and it has a positive eigenvector if the matrix is irreducible (the graph is connected or strongly connected). Moreover, if it is a primitive matrix then there is only one eigenvalue (largest eigenvalue) will be on the spectral circle.

I am trying to understand, what are the possible way to get undirected connected graphs which have repeated largest eigenvalue? In other words, the matrix is imprimitive. There is a test for primitivity which says: $A$ is primitive if and only if $A^m > 0$ for some $m > 0$, and no more than $n^2 - 2n + 2$ powers are required when $n$ is the dimension of $A$. [Ref: Google's PageRank and Beyond: The Science of Search Engine Rankings, Amy N. Langville and Carl D. Meyer]

I have calculated the eigenvalues in MATLABR2013a for a non-negative symmetric binary matrix which is also irreducible. The largest ten eigenvalues are as follows:

$5.8127684148732666\\ 5.8766485563836177\\ 5.9106703554270998\\ 5.9635014530912001\\ 5.9924101487069503\\ 6.0248904992311498\\ 6.1009778561888695\\ 6.2837952949876392\\ 11.4766987200153974\\ 11.4880733160807793$

For large matrices $n^2 - 2n + 2$ powers is very hard to do. By looking the largest two eigenvalues, can we say that the matrix is imprimitive? Or is there any theory so that we can say that a matix is near to imprimitive.

Also, I am facing a problem to identify degenerate eigenvalues. For instance, if we have a matrix A=[0 1 1 1;1 0 1 1;1 1 0 1;1 1 1 0]; we can calculate by hand the eigenvalues as $\{-1, -1, -1, 3\}$.

But, when we calculate the eigenvalues numerically, how can we say that there are degenerate eigenvalues? When we calculate eigenvalues numerically, how close a pair of eigenvalues such that we say that they are degenerate?

Note: I consider $A$ has all the diagonal elements are zero.

It will be a great help for me and thanks in advance for invaluable suggestion or link to some research article which discuss about the problems.



You must log in to answer this question.