Brauer’s ovals theorem
Let $A$ be a square complex matrix, ${R}_{i}={\sum}_{j\ne i}\left|{a}_{ij}\right|\mathit{\hspace{1em}}1\le i\le n$. Let’s consider the ovals of this kind: ${O}_{ij}=\{z\in \u2102:\left|z-{a}_{ii}\right|\left|z-{a}_{jj}\right|\le {R}_{i}{R}_{j}\}\mathit{\hspace{1em}}\forall i\ne j$. Such ovals are called Cassini ovals.
Theorem^{} (A. Brauer): All the eigenvalues^{} of A lie inside the union of these $\frac{n(n-1)}{2}$ ovals of Cassini:$\sigma (A)\subseteq {\bigcup}_{i\ne j}{O}_{ij}$.
Proof: Let $(\lambda ,\mathbf{v})$ be an eigenvalue-eigenvector pair for $A$, and let ${v}_{p},{v}_{q}$ be the components^{} of $\mathbf{v}$ with the two maximal absolute values^{}, that is $\left|{v}_{p}\right|\ge \left|{v}_{q}\right|\ge \left|{v}_{i}\right|\mathit{\hspace{1em}}\forall i\ne p$. (Note that $\left|{v}_{p}\right|\ne 0$, otherwise $\mathbf{v}$ should be all-zero, in contrast with eigenvector^{} definition). We can also assume that $\left|{v}_{q}\right|$ is not zero, because otherwise $A\mathbf{v}=\lambda \mathbf{v}$ would imply ${a}_{pp}=\lambda $, which trivially verifies the thesis. Then, since $A\mathbf{v}=\lambda \mathbf{v}$, we have:
$(\lambda -{a}_{pp}){v}_{p}={\sum}_{j=1,j\ne p}^{n}{a}_{pj}{v}_{j}$
and so
$\left|\lambda -{a}_{pp}\right|\left|{v}_{p}\right|=\left|{\sum}_{j=1,j\ne p}^{n}{a}_{pj}{v}_{j}\right|\le {\sum}_{j=1,j\ne p}^{n}\left|{a}_{pj}\right|\left|{v}_{j}\right|\le {\sum}_{j=1,j\ne p}^{n}\left|{a}_{pj}\right|\left|{v}_{q}\right|={R}_{p}\left|{v}_{q}\right|$
that is
$\left|\lambda -{a}_{pp}\right|\le {R}_{p}\frac{\left|{v}_{q}\right|}{\left|{v}_{p}\right|}$.
In the same way, we obtain:
$\left|\lambda -{a}_{qq}\right|\le {R}_{q}\frac{\left|{v}_{p}\right|}{\left|{v}_{q}\right|}$.
Multiplying the two inequalities, the two fractional terms vanish, and we get:
$\left|\lambda -{a}_{pp}\right|\left|\lambda -{a}_{qq}\right|\le {R}_{p}{R}_{q}$
which is the thesis.$\mathrm{\square}$
Remarks:
1) Much like the Levy-Desplanques theorem states a sufficient condition, based on Gerschgorin circles, for non-singularity of a matrix, Brauer’s theorem can be employed to state a similar^{} sufficient condition; namely, the following result of Ostrowski holds:
Corollary: Let $A$ be a $n\times n$ complex-valued matrix; if for all $i\ne j$ we have $\left|{a}_{ii}\right|\left|{a}_{jj}\right|>{R}_{i}{R}_{j}$, then $A$ is non singular^{}.
The proof is obvious, since, by Brauer’s theorem, the above condition excludes the point $z=0$ from the spectrum of $A$, implying this way $det(A)\ne 0$.
2) Since both Gerschgorin’s and Brauer’s results rely upon the same $2n$ numbers, namely ${\left\{{a}_{ii}\right\}}_{i=1}^{n}$ and ${\left\{{R}_{i}\right\}}_{i=1}^{n}$, one may wonder if Brauer’s result is stronger than Gerschgorin’s one; actually, the answer is positive^{}, as the following inclusion shows:
Corollary: Let $G(A)={\bigcup}_{i=1}^{n}{D}_{i}(A)$ and $B(A)={\bigcup}_{i\ne j}^{n}{O}_{ij}(A)$ be respectively Gershgorin and Brauer eigenvalues inclusion regions (${D}_{i}(A)$ are the Gerschgorin circles and ${O}_{ij}(A)$ are the Brauer’s Cassini ovals); then
$B(A)\subseteq G(A)$.
Proof: Let ${O}_{ij}$ be one of the $n(n-1)/2$ ovals of Cassini for matrix $A$ and be $z\in {O}_{ij}$. If ${R}_{i}=0$ or ${R}_{j}=0$, Brauer’s theorem imply $z={a}_{ii}$ or $z={a}_{jj}$ respectively; but since both ${a}_{ii}$ and ${a}_{jj}$ belong to their respective Gerschgorin circles, we have $z\in ({D}_{i}\cup {D}_{j})$. If both ${R}_{i}>0$ and ${R}_{j}>0$, then we can write:
$\frac{\left|z-{a}_{ii}\right|}{{R}_{i}}\cdot \frac{\left|z-{a}_{jj}\right|}{{R}_{j}}\le 1.$
For the left-hand side to be not greater than 1, $\frac{\left|z-{a}_{ii}\right|}{{R}_{i}}$ or $\frac{\left|z-{a}_{jj}\right|}{{R}_{j}}$ must be not greater than 1, which in turn means $z\in {D}_{i}$ or $z\in {D}_{j}$, that is $z\in ({D}_{i}\cup {D}_{j})$. This way, we proved that ${O}_{ij}\subseteq ({D}_{i}\cup {D}_{j})$; now, we have:
$B(A)={\bigcup}_{i\ne j}{O}_{ij}\subseteq {\bigcup}_{i=1}^{n}{D}_{i}=G(A)$.
3) It’s obvious from definition that there are infinitely many matrices which generate the same ovals of Cassini: namely, let’s define
$\mathrm{\Omega}(A)=\{M\in {\mathbf{C}}^{n\times n}:{m}_{ii}={a}_{ii},{R}_{i}(M)={R}_{i}(A)\}$
as the set of all matrices which share the same ovals of Cassini as $A$. Then, by Brauer’s theorem, we have, for all $M\in \mathrm{\Omega}$ matrices,
$$\sigma (M)\subseteq B(A),$$ |
and therefore, having defined $\sigma (\mathrm{\Omega})={\bigcup}_{M\in \mathrm{\Omega}}\sigma (M)$, we have
$$\sigma (\mathrm{\Omega})\subseteq B(A).$$ |
One may then ask how sharp this inclusion is, which, informally speaking, is equivalent^{} to asking how ”efficient” is the ”use”, by Brauer’s theorem, of the 2n pieces of information ${\left\{{a}_{ii}\right\}}_{i=1}^{n}$ and ${\left\{{R}_{i}\right\}}_{i=1}^{n}$ in the construction of inclusion sets (if for example we found the inclusion to be very loose, that is $\sigma (\mathrm{\Omega})$ to be a very little subset of $B(A)$, we could conjecture that the knowledge of the 2n numbers used by Brauer’s theorem should have led to a more precise bounding, since the spectra of all matrices which share these numbers lie in a much smaller region). It has been proven that actually
$$\sigma (\mathrm{\Omega})=B(A),$$ |
thus showing Brauer’s ovals are optimal ones under this point of view.
References
- 1 S. Gerschgorin, Uber die Abgrenzung der Eigenwerte einer Matrix, Isv. Akad. Nauk USSR Ser. Mat., 7 (1931), pp. 749-754
- 2 A. Brauer, Limits for the characteristic roots of a matrix II, Duke Math. J. 14 (1947), pp. 21-26
- 3 R. S. Varga and A. Krautstengl, On Gersgorin-type problems and ovals of Cassini, Electron. Trans. Numer. Anal., 8 (1999), pp. 15-20
- 4 Richard S. Varga, Gersgorin-type eigenvalue inclusion theorems and their sharpness,Electronic Transactions on Numerical Analysis. Volume 12 (2001), pp. 113-133
Title | Brauer’s ovals theorem |
---|---|
Canonical name | BrauersOvalsTheorem |
Date of creation | 2013-03-22 15:35:30 |
Last modified on | 2013-03-22 15:35:30 |
Owner | Andrea Ambrosio (7332) |
Last modified by | Andrea Ambrosio (7332) |
Numerical id | 15 |
Author | Andrea Ambrosio (7332) |
Entry type | Algorithm |
Classification | msc 15A42 |
Related topic | GershgorinsCircleTheorem |