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 ℂ:\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 ,𝐯)$ be an eigenvalue-eigenvector pair for $A$, and let $v_p,v_q$ be the components of $𝐯$ 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 $𝐯$ should be all-zero, in contrast with eigenvector definition). We can also assume that $\left|v_q\right|$ is not zero, because otherwise $A𝐯=\lambda 𝐯$ would imply $a_{pp}=\lambda$, which trivially verifies the thesis. Then, since $A𝐯=\lambda 𝐯$, 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 {𝐂}^{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.

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