2
$\begingroup$

We know from Perrone-Frobenius Theorem that the multiplicity of the largest eigenvalue is one when the matrix is positive (all elements strictly greater than zero) or when it's non-negative and irreducible.

Are there any other theorems regarding the uniqueness of the largest eigenvalue for matrices that contain both positive and negative elements?

EDIT: All my computer simulations/experiments tell me that the matrix I'm interested in has a unique largest eigenvalue. This has a very significant implication for the signal processing problem I'm working on. However, I cannot base my solution argument on "the simulations suggest that this matrix always has unique largest eigenvalue". I have to prove it. So let me add a few more information that I hope helps give a definitive proof.

My matrix is symmetric, positive definite of the form: $V^T WW^T V$. Where Both $V$ and $W$ are orthonormal bases. Specifically, $V$ is obtained by certain permutations of orthonormal basis $A$. Similarly, $W$ is also obtained by certain permutations of orthonormal basis $B$.

Now, $A$ contains a few left singular vectors of an entirely positive data matrix $X_1$. $B$ also contains a few left singular vectors of another entirely positive data matrix $X_2$.

Moreover, it is guaranteed (almost surely) that the elements of the matrix $V^T WW^T V$ are all non-zero. I.e. the associated digraph is strongly connected, or simply, $V^T WW^T V$ is irreducible.

Finally, $V^T WW^T V$ can be partitioned into square equal-sized blocks (thanks to certain conditions related to my problem).

Knowing (from experiments/simulations) that my matrix has a unique largest eigenvalue (that is very close to 1), and that it is unitarily diagonizable (because it's symmetric/normal), I tried something similar to the power iteration. Specifically, I raised the matrix $V^T WW^T V$ to a large integer power, say 1000, and pictured $(V^T WW^T V)^{1000}$ (using Matlab's imagesc) and what I got was an all zero matrix except for a non-zero element in the upper-left corner of each block (remember, under the conditioned of my problem, the matrix $V^T WW^T V$ is made up of square equal sized blocks). These non-zero elements all have the same value, which makes sense because with a distinct largest eigenvalue, the matrix $V^T WW^T V$ is bound to be of rank 1 when raised to a sufficiently large power (because all other eigenvalues of $V^T WW^T V$, being sufficiently smaller than 1, are bound to vanish when we raise the unitarily diagonizable $V^T WW^T V$ to a large enough power).

So far, it would seem to me that the only missing piece of information to complete the proof is the answer to the question: what are the conditions required to drive an irreducible symmetric positive definite matrix (made up of equal sized square blocks) into becoming all-zero except for a non-zero element in the corner of each one of its blocks, when raised to a large enough power? I'm probably looking for convergence properties of matrix power, when the matrix is as described above. Then again, maybe the power iteration idea is just a dead-end for my proof... and there is a better way of doing it.

EDIT2: Another obvious piece of information is that $WW^T$ is an orthogonal projection matrix, but I don't think it's very helpful.

Also, the fact that the data matrices mentioned above ($X_1$ and $X_2$) being entirely positive is irrelevant (I tried synthetic data matrices that contained both positive and negative elements, and the largest eigenvalue of $V^T WW^T V$ remains distinct).

BUT would that at least help us prove a sufficient condition? Specifically, because of the structure of $V^T WW^T V$ and certain other conditions of my problem, all the elements of $V^T WW^T V$ come from multiplications of sub-matrices of $A$ and $B$ (which are derived from ALL positive data matrices $X_1$ and $X_2$ as explained above).

In other words, I am willing to ignore that the data matrices ($X_1$ and $X_2$) don't have to be positive for a distinct largest eigenvalue (of $V^TWW^TV$), simply because it just so happens that the signals I'm dealing with (and thus the data matrices $X_1$ and $X_2$) are always positive. But even with an assumption of entirely positive $X_1$ and $X_2$, the issue would still be that it is required to compress positive $X_1$ and $X_2$ into $A$ and $B$, respectively (by taking only a few left singular vectors of each data matrix), which is the reason why, while blocks of $V^T WW^T V$ are irreducible (and thus the whole matrix is irreducible), the matrix still contains both positive and negative values (albeit it's ultimately based on strictly positive data matrices).

Again, my simulations verify that the data matrices $X_1$ and $X_2$ don't have to be positive for a distinct largest eigenvalue of $V^T WW^T V$, but IF POSSIBLE I'm willing to use the fact that the data matrices are always positive (for my problem) as a sufficient condition (based on some variation of Perrone-Frobenius theorem that admits an irreducible matrix that is derived from positive data matrices as described above).

SUMMARY: I'm looking at two different venues for a proof: power iteration convergence properties for my special matrix OR a variation of Perron-Frobenius theorem... are there any suggestions for how to continue on either path? Is there a third better option?

$\endgroup$
5
  • $\begingroup$ When you say that $V,W$ are orthonormal bases, do you mean that their columns are orthonormal vectors? Can you prove that the intersection of their column spaces (the columns spaces of V and W) is zero? $\endgroup$
    – Daniel
    Jan 19 '17 at 1:32
  • $\begingroup$ @Daniel Yes, the columns of $V$ are orthonormal, and the columns of $W$ are orthonormal. $\endgroup$
    – seeker
    Jan 19 '17 at 12:32
  • $\begingroup$ @Daniel I have a relevant question. Is there any known theorem that says something along the lines of: For a matrix with a certain special structure, the (algebraic) multiplicity of its eigenvalues are reflected by the multiplicity of its diagonal elements? Of course, the diagonal elements of a diagonal matrix are its eigenvalues, but I'm asking if there are other (known) types of matrices whose diagonal elements spell out the multiplicity of the eigenvalues? If the answer is positive, then I could probably solve the problem. $\endgroup$
    – seeker
    Jan 19 '17 at 12:46
  • $\begingroup$ In general the answer for this question is no. There is no connection between the multiplicity of the diagonal elements and the eigenvalues. Let $A$ be any Hermitian matrix, we can find a unitary matrix $U$ such that the diagonal elements of $UAU^*$ are equal. Notice that $UAU^*$ and $A$ have the same spectrum. However, if the gershgorin's disks are disjoint (i.e. the elements of the diagonal are very far apart) then the eigenvalues are different ( math.stackexchange.com/questions/474800/…). $\endgroup$
    – Daniel
    Jan 19 '17 at 13:43
  • $\begingroup$ I believe the key for solving this problem is Cauchy interlacing theorem. $\endgroup$
    – Daniel
    Jan 19 '17 at 13:43
3
$\begingroup$

There's a result known as the Gershgorin circle theorem concerning eigenvalue estimation for any square matrix (see https://en.wikipedia.org/wiki/Gershgorin_circle_theorem). In short, it states that we can easily associate to any $n\times n$ matrix a set of $n$ disks in the complex plane, each centered at a diagonal entry of $A$, and such that the eigenvalues of $A$ are contained in the union of the disks. Furthermore, if there are $k$ disks whose union does not intersect the remaining $n-k$, then these $k$ disks contain exactly $k$ of the eigenvalues. In particular, an isolated disk will contain exactly one eigenvalue of $A$.

Back to your question: suppose that $A=(a_{i,j})$ is an $n\times n$ matrix. Using the notation from the page linked above, let $R_i=\sum_{j\neq i}|a_{i,j}|$ be the $i^{th}$ row sum and $D(a_{i,i},R_i)$ denote the $i^{th}$ Gershgorin disk. Suppose that for some $i$ we have $$|a_{i,i}|-|a_{j,j}|>R_i+R_j$$ for all $j\neq i$. Equivalently, suppose that some $i$ satisfies $$|a_{i,i}|-R_i>|a_{j,j}|+R_j$$ for all $j\neq i$. Since $D(a_{i,i},R_i)$ is a disk with center $a_{i,i}$ and radius $R_i$, this inequality states that every element of $D(a_{i,i},R_i)$ is farther from the origin than any element in any of the remaining disks $D(a_{j,j},R_j)$. That is, $D(a_{i,i},R_i)$ is an isolated disk with $|\lambda|>|\mu|$ for all $\lambda\in D(a_{i,i},R_i)$ and all $\mu\in D(a_{j,j},R_j)$ with $j\neq i$ (draw a picture to see what's going on here). The fact that $D(a_{i,i},R_i)$ is isolated guarantees that it contains exactly one eigenvalue of $A$, and the above analysis ensures it is the largest in modulus.

Note: this argument applies equally well when we consider column sums instead of row sums, as $A$ and $A^T$ have the same eigenvalues.

$\endgroup$
3
  • $\begingroup$ @seeker Edit your question by adding the information regarding your actual problem. Add the definitions of quasi-orthogonal and dense matrices. $\endgroup$
    – Daniel
    Jan 17 '17 at 17:16
  • $\begingroup$ Thanks @Zack Cramer for the detailed response. I edited my question for more information. $\endgroup$
    – seeker
    Jan 18 '17 at 10:33
  • $\begingroup$ @Daniel, thanks for your advice. $\endgroup$
    – seeker
    Jan 18 '17 at 10:33

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.