# Brauer’s ovals theorem

Let $A$ be a square complex matrix, $R_{i}=\sum_{j\neq i}\left|a_{ij}\right|\quad 1\leq i\leq n$. Let’s consider the ovals of this kind: $O_{ij}=\left\{z\in\mathbb{C}:\left|z-a_{ii}\right|\left|z-a_{jj}\right|\leq R_% {i}R_{j}\right\}\quad\forall i\neq 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\neq 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|\geq\left|v_{q}\right|\geq\left|v_{i}\right|\quad\forall i\neq p$. (Note that $\left|v_{p}\right|\neq 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\neq p}^{n}a_{pj}v_{j}$

and so

$\left|\lambda-a_{pp}\right|\left|v_{p}\right|=\left|\sum_{j=1,j\neq p}^{n}a_{% pj}v_{j}\right|\leq\sum_{j=1,j\neq p}^{n}\left|a_{pj}\right|\left|v_{j}\right|% \leq\sum_{j=1,j\neq p}^{n}\left|a_{pj}\right|\left|v_{q}\right|=R_{p}\left|v_{% q}\right|$

that is

$\left|\lambda-a_{pp}\right|\leq R_{p}\frac{\left|v_{q}\right|}{\left|v_{p}% \right|}$.

In the same way, we obtain:

$\left|\lambda-a_{qq}\right|\leq 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|\leq R_{p}R_{q}$

which is the thesis.$\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\neq 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)\neq 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\neq 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}}% \leq 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\neq 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

$\Omega(A)=\left\{M\in\mathbf{C}^{n\times n}:m_{ii}=a_{ii},R_{i}(M)=R_{i}(A)\right\}$

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\Omega$ matrices,

 $\sigma(M)\subseteq B(A),$

and therefore, having defined $\sigma(\Omega)=\bigcup_{M\in\Omega}\sigma(M)$, we have

 $\sigma(\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(\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(\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 BrauersOvalsTheorem 2013-03-22 15:35:30 2013-03-22 15:35:30 Andrea Ambrosio (7332) Andrea Ambrosio (7332) 15 Andrea Ambrosio (7332) Algorithm msc 15A42 GershgorinsCircleTheorem