3
$\begingroup$

I have two matrices

$$ A=\begin{pmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 & 0 & c \end{pmatrix} \quad \text{ and } \quad B=\begin{pmatrix} d & e & f \\ d & e & f \\ d & e & f \end{pmatrix} $$

In reality mine are more like 1000 x 1000 matrices but the only thing that is important for now is that the left matrix is diagonal and the right one has one row that repeats itself.

Obviously the eigenvalues of the left matrix are its diagonal components. I want to create a new matrix C

$$C = A+B=\begin{pmatrix} a & 0 & 0 \\0 & b & 0 \\0 & 0 & c \end{pmatrix}+\begin{pmatrix} d & e & f \\d & e & f \\d & e & f \end{pmatrix}=\begin{pmatrix} a+d & e & f \\d & b+e & f \\d & e & c+f \end{pmatrix}$$

I am now wondering how the eigenvalues of this new matrix C are related to the eigenvalues of the diagonal matrix A. Can I use an argument that uses row reduction in order to relate the eigenvalues of both matrices?

The reason why I am asking is that my 1000 x 1000 matrix (implemented in mathematica) that is described as above gives me almost the same eigenvalues as the corresponding diagonal matrix (only a few eigenvalues differ) and I really cannot think of any reason why that should be the case.

EDIT:

I implemented a simple code in mathematica to illustrate what I mean. One can see that every eigenvalue of the diagonal matrix A appears in C:

    dim = 50;

    A = DiagonalMatrix[Flatten[RandomInteger[{0, 10}, {1, dim}]]];

    mat = RandomReal[{0, 100}, {1, dim}];
    B = ArrayFlatten[ConstantArray[{mat}, dim]];

    c = A + B;

    Abs[Eigenvalues[A]]
    Round[Abs[Eigenvalues[c]], 0.01]

    (*{10, 10, 10, 10, 10, 10, 9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 
    6, 6, 6, 6, 5, 5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 
    1, 1, 1, 0, 0, 0}*)

    (*{2084.89, 10., 10., 10., 10., 10., 9.71, 9., 9., 9., 9., 9., 8.54, 
    8., 8., 8., 7.72, 7., 7., 7., 7., 6.61, 6., 6., 6., 5.44, 5., 5., 5., 
    5., 4.29, 4., 4., 4., 3.51, 3., 3., 3., 3., 2.28, 2., 2., 2., 2., 
    1.21, 1., 1., 0.33, 0., 0.}*)

$\endgroup$
  • $\begingroup$ Assuming you didn't mean for your matrix $B$ to look like that I'd look at eigenvalue perturbation resources. I think there is a closed form in some cases. $\endgroup$ – user3417 Aug 11 '19 at 23:22
  • $\begingroup$ Actually if the eigenvalues of $A$ are distinct, one can place the eigenvalues of $C$ arbitrarily by a proper choice of such $B$. $\endgroup$ – A.Γ. Aug 12 '19 at 0:07
  • $\begingroup$ Please see my edited question $\endgroup$ – xabdax Aug 12 '19 at 0:48
  • 1
    $\begingroup$ x-posted on mathematica.se: mathematica.stackexchange.com/q/203614/34893 $\endgroup$ – AccidentalFourierTransform Aug 12 '19 at 1:47
  • $\begingroup$ The search term for this question is "rank one perturbation". $\endgroup$ – Gerry Myerson Aug 12 '19 at 4:10
6
$\begingroup$

The phenomenon you're observing happens because your example is not a generic one, but have many repeated eigenvalues.

First, if all the eigenvalues of $A$ are distinct then the rank-one perturbation $A+bk^T$ may have an arbitrary set of eigenvalues iff the pair $(A,b)$ is controllable, or equivalently the matrix $R=[b\ Ab\ \ldots\ A^{n-1}b]$ is of full rank. The result is known as the pole placement in control theory. In our case, $b=[1\ 1\ \ldots\ 1]^T$ and $R$ becomes the Vandermonde matrix, which is clearly invertible under our assumption on the eigenvalues of $A$. Conclusion: in general, you cannot say anything about the perturbed eigenvalues if you just know the eigenvalues of $A$ and not the perturbation.

What happens if the eigenvalues are repeated as in your example? Define $A=\operatorname{diag}\{a_i\}$. Introduce the polynomials $$ p(\lambda)=\det(\lambda I-A)=\prod_{i=1}^n(\lambda-a_i),\qquad p_i(\lambda)=\frac{p(\lambda)}{\lambda-a_i}=\prod_{j\ne i}(\lambda-a_j), $$ and calculate the characteristic polynomial for $A+bk^T$ using Sylvester's determinant theorem \begin{align} \det(\lambda I-A-bk^T)=p(\lambda)(1-k^T(\lambda I-A)^{-1}b)=p(\lambda)-\sum_{i=1}^n k_ib_ip_i(\lambda). \end{align} Note that all the polynomials are going to have the common factor $\lambda-a$ if $a$ is an eigenvalue of multiplicity more than $1$, thus, this $a$ is a perturbed eigenvalue as well. It has got the multiplicity one less than that of the corresponding eigenvalue in $A$. This is what you see in your numerical example. Hence the rule is

If you have an eigenvalue $a$ for $A$ of multiplicity $k>1$ then you gonna have the same perturbed eigenvalue $a$ for $A+bk^T$ of multiplicity at least $k-1$.


EDIT: A simple example, take $A=I$, the $n\times n$ identity matrix. Then $$ \det(\lambda I-I-bk^T)=\det((\lambda-1)I-bk^T)=[\mu=\lambda-1]=\det(\mu I-bk^T)=0. $$ The eigenvalues of the rank-one matrix $bk^T$ are $n-1$ zeros and one more whatever. Those $n-1$ zeros for $\mu$ are $n-1$ ones for $\lambda$.

$\endgroup$
  • 1
    $\begingroup$ Thanks --- I learned a lot from this! $\endgroup$ – John Hughes Aug 12 '19 at 14:31
  • $\begingroup$ This is a very helpful answer! Thanks! Can I generalize what you wrote with a vector that consists of matrices (instead of rows) that repeat themselves? Let's say we have some arbitrary square matrices D, E, F, ... of dimension n>1, then define the k in your answer to be $$k=\begin{pmatrix} D & E & F & \cdots \end{pmatrix}^T$$ Eventually you will get a big matrix that looks something like $$bk^T=\begin{pmatrix} D & E & F & \cdots\\ D & E & F & \cdots\\ D & E & F & \cdots\\ \vdots&\vdots&\vdots&\ddots \end{pmatrix}$$ $\endgroup$ – xabdax Aug 12 '19 at 16:49
  • $\begingroup$ @xabdax It seems possible to do a generalization in this direction, but one can only assure the multiplicity $k-m$ for the perturbed eigenvalue where $m$ is the size of the square blocks $D$, $E$, $F$ etc. $\endgroup$ – A.Γ. Aug 12 '19 at 18:26
  • $\begingroup$ Can one generalize the above proof to a diagonal matrix that gets two rank-one updates instead of one, i.e. $D + bk^T + uv^T$, where u and v have the same dimension as b and k, but different values? $\endgroup$ – xabdax Feb 15 at 22:52
  • $\begingroup$ Please see my updated question $\endgroup$ – xabdax Feb 16 at 17:50
2
$\begingroup$

Your second matrix has rank $1$, because every row is a linear combination of the first row (namely, they're equal).

That means that the kernel is $n-1$-dimensional. If you're lucky, many of the eigenvectors $A$ lie in or near that kernel, in which case $$ (A+B)v = Av + Bv = Av + 0 = Av = \lambda_v v $$ so it's still an eigenvector with the same eigenvalue.

That this does not happen in general is well illustrated in 3-space by picking $(d,e,f)$ so that none of the standard basis vectors are perpendicular to it (i.e., none lie in the kernel of $B$). If you pick $(d,e,f) = (6,6,6)$, and $(a,b,c)=(4,-2, 8)$, for instance, you'll find that the eigenvalues of the sum differ substantially from those of $A$. Here's a transcript of a matlab session demonstrating this:

>> A = diag([4, -2, 8], 0)

A =

     4     0     0
     0    -2     0
     0     0     8

>> B = repmat([6,6,6], 3, 1)

B =

     6     6     6
     6     6     6
     6     6     6

>> eig(A)

ans =

    -2
     4
     8

>> eig(A+B)

ans =

   -0.1217
    5.9193
   22.2024

So for your big matrix, either (a) many of the standard basis vectors are nearly eigenvectors of $B$ (perhaps because the "row" in $B$ has lots of small-ish entries, compared to those in $A$, or the eigenvalues of $A$), or (b) something far weirder is happening, and it's because of the structure of the matrices that you're getting this phenomenon. I'm betting on case "a", but that's just a wild guess.

$\endgroup$
  • $\begingroup$ Please see my edited question. $\endgroup$ – xabdax Aug 12 '19 at 0:48
  • $\begingroup$ So roughly: your matrix $A$ is, in fact, special, in that it has small integer entries, hence many repeated eigenvalues, and hence @A.Γ.'s answer explains things, and this is consistent with case "b" of my answer. My answer explains what happened in the question you originally asked, where you stressed that the only important things were "A diagonal" and "B is rank 1". $\endgroup$ – John Hughes Aug 12 '19 at 12:00

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.