MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

I have an asymmetric square matrix with non-negative real entries in the range [0,10], representing the edge-weights of a directed network. Assume that the network is a linear system. My general question is the following: how far can I go about destroying any structural patterns present in the network, while preserving its maximum eigenvalue?

Say I have an asymmetric 10 X 10 matrix M, whose absolute value of the maximum eigenvalue is v. Say M has 70 non-zero entries in the range (0,10] and the rest 0. Now, the questions:

(1) Does v depend on the number of non-zero entries of the matrix? So suppose I randomly replace some n zero-entries with values from (0,10], or replace n non-zero entries with 0, does the maximum eigenvalue v of the new matrix change predictably with n?

(2) Does v depend on the sum of non-zero entries of M? So if I randomly pick pairs of non-zero entries, and replace one of them with their sum and the other with 0, will v be sensitive to it?

(3) Does v depend on the spatial distribution or configuration of the non-zero entries of M? So, if I randomly shuffle around the non-zero entries, how much can I expect v to vary? Are there any bounds to v subject to all possible shuffling configurations?

If the answers are NO to the above questions, then I will have at least 3 ways of modifying (possibly randomly) the connection structure and the edge weights of M, while subjecting it to the constraint that its maximum eigenvalue v stays constant or at least within some range v +/- x.


share|cite|improve this question

Seems to me that all of your proposed modifications can lead to big changes in the maximum absolute value of the eigenvalues. For (1), consider $$\pmatrix{10&0\cr0&1\cr}{\rm\ and\ }\pmatrix{0&0\cr0&1\cr}$$ For (2), $$\pmatrix{5&0\cr0&5\cr}{\rm\ and\ }\pmatrix{10&0\cr0&0\cr}$$ For (3), $$\pmatrix{10&1\cr0&1\cr}{\rm\ and\ }\pmatrix{1&10\cr0&1\cr}$$

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.