MATH 417 Lecture 21

« previous | Tuesday, April 8, 2014 | next »

Special Matrices

• (strictly) Diagonally Dominant: Failed to parse (unknown function "\nej"): {\displaystyle a_{ii} > \sum_{i\nej} (a_{ij})}
• (strictly) Positive Definite: $A=A^T$

Both types are nonsingular, and

Theorem. If $A$ is diagonally dominant, then we can perform gaussian elimination without pivoting: $A=LU$; $L=\left[\begin{array}{cc}1& 0\\ {\ell }_{ij}& 1\end{array}\right]$; $U=\left[\begin{array}{cc}{u}_{11}& u_{ij}\\ 0& u_{nn}\end{array}\right]$

Proof. After one step of gaussian elimination, we go from matrix $A^{(1)}$ to $A^{(2)}$, where $a_{i1}^{(2)}=0$ for $i\ne 1$ by adding (row 1) × $-\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}$ to the $i$-th row:

$a_{ij}^{(2)}=a_{ij}^{(1)}-\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}{a}_{1j}^{(1)}$

This is possible because $a_{11}\ne 0$ by the diagonally dominant property:

$\begin{array}{rl}\sum _{j\ne i}\left|a_{ij}^{(2)}\right|& =\sum _{j\ne i}|a_{ij}^{(1)}-\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}{a}_{1j}^{(1)}|\\ & \le \sum _{j\ne i}\left|a_{ij}^{(1)}\right|+\sum _{j\ne i}\left|\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}\right|\cdot \left|a_{1j}^{(1)}\right|\\ & \le \underset{\text{row}i}{\underbrace{\left|a_{ii}^{(1)}\right|-\left|a_{i1}^{(1)}\right|}}+\left|\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}\right|\left(\underset{<\left|a_{11}^{(1)}\right|-\left|a_{1i}^{(1)}\right|}{\underbrace{\sum _{j=2}^n\left|a_{1j}^{(1)}\right|}}\right)\\ & <\left|a_{ii}^{(1)}\right|-\left|\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}{a}_{1i}^{(1)}\right|\\ & \le a_{ii}^{(2)}\end{array}$

The theorem holds by induction.

quod erat demonstrandum

Theorem. If $A$ is positive definite, then

$a_{ii}>0$ for $i=1,2,\dots ,n$
$a_{ij}^2<a_{ii}{a}_{ij}$ for $i\ne j$
$\underset{1\le i,j\le n}{\max }\left|a_{ij}\right|=\underset{1\le i\le n}{\max }\left|a_{ii}\right|$

Proof. Let $A$ be a $n\times n$ matrix with entries $\left(a_{ij}\right)$

By definition, we have $A=A^T$ (or $A=\overline{A^T}$, if $a\in {\mathbb{ℂ}}_n$)

Define the minor of matrix $A$ to be:

$M_{ii}=\left[\begin{array}{ccc}{a}_{11}& \dots & a_{1i}\\ ⋮& \ddots & ⋮\\ a_{i1}& \dots & a_{ii}\end{array}\right]$ for $i=1,2,\dots ,n$

Lemma: $A$ is positive definite if and only if $\left|M_{ii}\right|>0$.

Let's start with $n=1$:

$A=\left(a_{11}\right)$, $\overrightarrow{x}=(x_1)\ne 0$. ${\overrightarrow{x}}^{T}A\overrightarrow{x}=a_{11}{x}^2>0$ if and only if $a_{11}>0$

For $n=2$:

$A=\left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right]$, and $\overrightarrow{x}=⟨x_1,x_2⟩$.

We have ${\overrightarrow{x}}^{T}A\overrightarrow{x}=F(x_1,x_2)=a_{11}{x}_1^2+2a_{12}{x}_1{x}_2+a_{22}{x}_2^2$. If $\overrightarrow{x}=⟨1,0⟩$, then $a_{11}>0$; if $\overrightarrow{x}=⟨0,1⟩$, then $a_{22}>0$; and for any other $\overrightarrow{x}$, we have $a_{12}^2<a_{11}{a}_{12}$

For the general case, let $\overrightarrow{x}={\hat{e}}_i=⟨0,0,\dots ,1,\dots ,0⟩$. Then ${\overrightarrow{x}}^{T}A\overrightarrow{x}=a_{ii}$.

If $\overrightarrow{x}={\hat{e}}_i+{\hat{e}}_j$, then ${\overrightarrow{x}}^{T}A\overrightarrow{x}$ gives $(a_{ii}{x}_i+a_{ji}{x}_j)x_i+(a_{ij}{x}_i+a_{jj}{x}_j)x_j=a_{ii}{x}_i^2+2a_{ij}{x}_i{x}_j+a_{jj}{x}_j^2$. This is positive if and only if the diagonal entries are positive.

To prove the final property, let $x_i=1$ and $x_j=-1$ in the previous part. Then ${\overrightarrow{x}}^{T}A\overrightarrow{x}=a_{ii}-2a_{ij}+a_{jj}>0$.

Now let $x_i=1$ and $x_j=1$. Then ${\overrightarrow{x}}^{T}A\overrightarrow{x}=a_{ii}+2a_{ij}+a_{jj}>0$.

Hence $\left|a_{ij}\right|<\frac{a_{ii}+a_{jj}}{2}<\underset{1\le i\le n}{\max }{a}_{ii}$

quod erat demonstrandum

These conditions are necessary, but not sufficient.

Section 7.1: Norms

In general, solving $A\overrightarrow{x}=\overrightarrow{b}$ for $\overrightarrow{x}$ costs $O(n^3)$.

If $A$ is a good matrix (not identity) positive definite, given $ϵ>0$, find $x^{(1)},x^{(2)},\dots ,x^{(k)}$ such that $|x^{(}k)-x|\le ϵ$ and $|A{x}^k-b|<ϵ$

Let $V$ be a linear space (closed on addition and scalar multiplication)

Definition. $\Vert \cdot \Vert$ is a norm if:

1. $\Vert x\Vert \ge 0$ for $x\in V$
2. $\Vert \alpha x\Vert =\left|\alpha \right|\Vert x\Vert$ for all scalars $\alpha$
3. $\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert$.

Most important vector norms:

1. ${\Vert \overrightarrow{x}\Vert }_{\mathrm{\infty }}=\underset{1\le i\le n}{\max }\left|x_i\right|$
2. ${\Vert \overrightarrow{x}\Vert }_p={\left(\sum _{i=1}^n{\left|x_i\right|}^p\right)}^{\frac{1}{p}}$ for $1\le p<\mathrm{\infty }$