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

eigenvalues-eigenvectorsmatricesreference-requestsymmetric matrices

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.

Best Answer

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$.

Related Question