Effect of Scaling a Row and Column on Multiplicities of Nonzero Eigenvalues of a Symmetric Matrix

Question

Question:

Let $A$ be a real symmetric $n\times n$ matrix with eigenvalues $\lambda_1, \lambda_2,\cdots, \lambda_n $ and corresponding algebraic multiplicities $a_1, a_2, \cdots, a_n$.

Consider a scaling operation where we scale the $i_1$-th, $i_2$-th, $\cdots$, $i_m$-th rows and corresponding columns of $A$ by scalars $c_1, c_2, \cdots, c_m$, respectively, where each $c_k > 0$ is different and $c_k \ne 1$. This operation results in a new matrix $B$, which can be represented as $B=DAD$ where $D$ is a diagonal matrix with $D_{i_ki_k} = c_{i_k}$ and other diagonal entries as 1.

How does this scaling operation affect the nonzero eigenvalues and their algebraic multiplicities? Specifically, does the scaling operation reduce the algebraic multiplicities of the nonzero eigenvalues?

Observation:

During my matrix experiments, I occasionally observed that all algebraic multiplicities $a_i$ (larger than $m$) of nonzero eigenvalues become $a_i-m$ after the scaling operation. In a simpler case, suppose there exist only $a$ repeated nonzero eigenvalues; after random scaling on $m$ rows and corresponding columns of $A$, the resulting matrix $B$ only has $a-m$ repeated nonzero eigenvalues, and those repeated nonzero eigenvalues of $B$ are the same with $A$'s.

I do not know why this happens. Is this situation guaranteed to be true?

Any insights, references, or suggestions for further reading would be greatly appreciated.

EDIT: In below code I generate the symmetric matrix $A \in\mathbb{R}^{10 \times 10}$ by $A = U \Sigma U^T$. And $\Sigma \in\mathbb{R}^{10\times 10}$ is a diagonal matrix and $U\in\mathbb{R}^{10\times 10}$ is a random orthogonal matrix. Then, I choose the identity diagonal matrix $D$, randomly select 2 entries, and randomly perturb them. Finally, I compute eigenvalues of $DAD$.

Note that in below codes, the eigenvalues of $A$ is $[81, 81, 81, 81, 25, 25, 25, 4, 0, 0]$.

import random
import numpy as np
from scipy.linalg import eigh
from scipy.stats import ortho_group

Sigma = np.array([[81, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 81, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 81, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 81, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 25, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 25, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 0, 25, 0, 0, 0],
                  [0, 0, 0, 0, 0, 0, 0, 4, 0, 0],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
U = ortho_group.rvs(dim=10)
A = U @ Sigma @ U.T
D = np.eye(10)
indices = random.sample(range(n), 2)
for i in indices:
    D[i, i] *= abs(random.gauss(0, 1))
print(eigh(D @ A @ D)[0])

First result of eigenvalues of $DAD$:

[-2.01362961e-16  4.68941727e-14  3.64694304e+00  1.99456413e+01
  2.50000000e+01  2.56321755e+01  6.47533258e+01  8.10000000e+01
  8.10000000e+01  8.52550236e+01]

Second result of eigenvalues of $DAD$:

[4.18632562e-14 5.63744673e-14 1.75155205e+00 3.91381351e+00
 2.35508874e+01 2.50000000e+01 6.28954663e+01 7.65616023e+01
 8.10000000e+01 8.10000000e+01]

I can try more, but still, there are two 81 and one 25 in the eigendecomposition.

Answer 1

I will stick to the case where $A$ is positive definite (i.e. $A$ has positive eigenvalues), and the scaling values are taken from the interval $(0,1)$ but I suspect that something can be said more generally.

Let $m$ denote the number of scaling operations. Note that the matrix $DAD$ is similar to (and thus has the same eigenvalues as) the symmetric matrix $$ (DA^{1/2})^{-1}[DAD]DA^{1/2} = A^{1/2}D^2 A^{1/2} $$ On the other hand, $D^2$ can be written as $D^2 = I - P$, where $P$ is diagonal with $m$ positive entries. Thus, we can write $$ A^{1/2}D^2 A^{1/2} = A^{1/2}(I - P)A^{1/2} = A^{1/2}A^{1/2} - APA^{1/2} = A - APA^{1/2}. $$ That is, we have $A^{1/2}DA^{1/2} = A - Q$ for some symmetric positive definite matrix $Q$ with rank $m$.

Now, let $\mu_1\geq \cdots\geq \mu_n$ denote the eigenvalues of $A$, and $\nu_1 \geq \cdots \geq \nu_m \geq \nu_{m+1} = \cdots = \nu_{n} = 0$ the eigenvalues of $Q$. If $\lambda_1 \geq \cdots \geq \lambda_n$ denote the eigenvalues of $A - Q$, then for all $i$ we have $$ \mu_{i + j} - \nu_{1 + j} \leq \lambda_i \leq \mu_{i + j} - \nu_{n - j}, \quad j = 0,\dots,n-1. $$ Now, suppose for instance that $A$ has repeated largest eigenvalues $\mu_1 = \mu_2 = \cdots = \mu_{p}$ with $p > m$. On the one hand, we have (setting $i = 1$ and setting $j = m$ for the lower bound and $j = 0$ for the upper bound), $$ \mu_{m+1} - \nu_{m+1}\leq \lambda_1, \quad \lambda_1 \leq \mu_{1} - \nu_n \implies\\ \mu_{m+1} \leq \lambda_1 \leq \mu_1. $$ Thus, we guarantee that $\lambda_1 = \mu_1$. That is, $A$ has the same repeated largest eigenvalue with multiplicity at least 1. Repeating the above for $i = 1,\dots, (p-m)$, we similarly have $$ \mu_{m+2} \leq \lambda_2 \leq \mu_2, \quad \dots, \quad \mu_p \leq \lambda_{p-m} \leq \mu_{p-m}. $$ Thus, we guarantee that $A - Q$ has the eigenvalue $\lambda_1$ with multiplicity at least $q - m$.

A similar manipulation of these inequalities can be used to show that in general, if $A$ has any eigenvalue (not necessarily the greatest) with multiplicity $p > m$, then $A - Q$ is guaranteed to have the same eigenvalue with multiplicity at least $p - m$.

Answer 2

Let $A = \text{diag}(\lambda_1,\dots,\lambda_n)$ be a diagonal matrix, so its eigenvalues are $\lambda_i$. The eigenvalues of $DAD$ are then $d_{ii}^2 \lambda_i$, where $d_{ii}$ may be $1$ if the corresponding row/column is not scaled. Therefore in principle one can go from pretty much any eigenvalues/multiplicities to any other eigenvalues/multiplicities, as long as we maintain the non-negativity (or non-positivity) of the eigenvalues in this example.

I suppose depending on how one defines "random scaling" one could probably say something more meaningful. Speaking intuitively, a random real symmetric matrix is extremely unlikely to have eigenvalues with repeated multiplicity, so any kind of random perturbation to it (such as "random scaling") should destroy this structure. I do not know much more about spectral perturbations though.

Here is a slight modification of the code from the question edited so that $U$ is the identity matrix.

import random
import numpy as np

random.seed(1)
for j in range(10):
    sigma = np.array([81,81,81,81,25,25,25,4,0,0])
    n = sigma.shape[0]
    D = np.ones(n)
    indices = random.sample(range(n), 2)
    for i in indices:
        D[i] *= np.abs(random.gauss(0, 1))
    print("attempt=%d" % j)
    print(np.sort(D*sigma*D))

This yields the output

attempt=0
[  0.           0.           0.11237516   4.          25.
  25.          25.          81.          81.         110.70514715]
attempt=1
[ 0.          0.          4.17877956 25.         25.         25.
 81.         81.         81.         81.        ]
attempt=2
[  0.           0.           0.45363746  25.          25.
  25.          81.          81.          81.         283.45996987]
attempt=3
[ 0.          0.          1.72545761  4.         25.         25.
 44.58038381 81.         81.         81.        ]
attempt=4
[ 0.          0.          1.6960394   3.33691544  4.         25.
 25.         25.         81.         81.        ]
attempt=5
[  0.           0.           4.          25.          25.
  25.          81.          81.          81.         344.00374728]
attempt=6
[ 0.          0.          2.77547143  4.         25.         25.
 36.64294613 81.         81.         81.        ]
attempt=7
[ 0.          0.          3.03275028 25.         25.         25.
 81.         81.         81.         81.        ]
attempt=8
[  0.           0.           1.8245589   25.          25.
  25.          81.          81.          81.         385.96340176]
attempt=9
[ 0.          0.          4.          4.10602215 25.         25.
 81.         81.         81.         81.        ]

Using elementary probability theory we can compute the probabilities of multiplicities of $81$s being reduced, or $25$s, or both, or neither in this simple model. My point is that the answer to your question

Is this situation guaranteed to be true?

is clearly not in general.