\chapter{Important Results from Linear Algebra}\label{C:Linear_Algebra_Appendix}

\noi What follows is a list of results from linear algebra that are referenced at various
places in this text. Further elaboration on each of them can be found in a variety
of other sources, such as \cite{Horn_Johnson} and \cite{Lay}. We assume in this
list of results that all matrices have real-valued entries.
\section{Linear Independence}\label{S:LinearIndependence}

\noi Suppose that $\ds V=\left\{ \vecv_1, \vecv_2, \ldots, \vecv_n \right\}$ is
a set of vectors in $\R^m$ and that $A$ is the $m$-by-$n$ matrix having these vectors
as columns. Then $V$ is a set of linear independent
vectors if and only if the homogeneous matrix equation
$A \vecx = \zerovec$ has only the trivial solution, $\vecx=\zerovec$.

\section{The Invertible Matrix Theorem}\label{S:InvertibleMatrixTheorem}
\begin{theorem}
Suppose that $A$ is an $n$-by-$n$ matrix.
Then the following conditions are logically
equivalent.
\be
\item The determinant of $A$ is nonzero.
\item The reduced row echelon form of $A$ is $I_n$, the $n$-by-$n$ identity matrix.
\item $A$ is invertible.
\item The set of column vectors of $A$ and the set of row
vectors of $A$ both span $\R^n$.
\item The set of column vectors of $A$ and the set of row
vectors of $A$ both form linear independent sets.
\item The set of column vectors of $A$ and the set of row
vectors of $A$ both form a basis for $\R^n$.
\item The homogeneous matrix equation $A\vecx=\zerovec$ has only
the trivial solution, $\vecx=\zerovec$.
\item For every vector $\vecb$ in $\R^n$ the matrix equation
$A \vecx=\vecb$ has a unique solution given by $\ds \vecx = A^{-1}\vecb.$
\item The column space of $A$ has dimension $n$ and the null space of $A$ has dimension zero.
\item Zero is not an eigenvalue of $A$.
\ee
\end{theorem}

\section{Transpose Properties}\label{S:TransposeProperties}

\noi The transpose of an $m$-by-$n$ matrix $A$, written $A^t$, is the $n$-by-$m$ matrix obtained by interchanging the rows and columns of $A$. Important properties of
the transpose include the following:
\be
\item $\left(A^t \right)^t = A$.
\item $\left(A+B\right)^t = A^t+B^t$, for any other $m$ by $n$ matrix, $B$.
\item $\left(AB\right)^t = B^t A^t$, provided the matrix product $AB$ is defined.
\item $\det\left(A^t\right) = \det(A)$.
\item If $A$ is a square, invertible matrix, then so is $A^t$, and
$\ds \left(A^t \right)^{-1} = \left(A^{-1}\right)^t$.
\item If $\vecu$ and $\vecv$ are column vectors in $\R^n$, then
$\ds \vecu^t \vecv = \vecv^t \vecu$. In particular, if
$\vecu$ is a column vector in $\R^n$, then $\vecu^t \vecu = \| \vecu \|^2$.
\item The Cauchy-Schwartz Inequality\index{Cauchy-Schwartz Inequality}:
$\ds \left| \vecu^t \vecv \right| \leq \| \vecu \| \| \vecv \|$ for every
pair of column vectors $\vecu$ and $\vecv$ in $\R^n$, with equality occurring if and only
if $\vecu$ and $\vecv$ are scalar multiples of one another.
\item If $A$ is an $n$-by-$n$ matrix, then the eigenvalues of $A^tA$ are all
nonnegative. For a symmetric matrix, $A$, $A^tA=A^2$. Since each eigenvalue
of $A^2$ is the square of an eigenvalue of $A$, it follows that the
eigenvalues of a symmetric matrix are all real-valued.
\ee

\section{Positive Definite Matrices}\label{S:PositiveDefiniteMatrices}

\noi A symmetric, $n$-by-$n$ matrix, $Q$, is positive definite if and only if
$\ds \vecx^t Q \vecx >\zerovec$ for all $\vecx$ in $\R^n$. Equivalently, $Q$
is positive definite if and only if its eigenvalues are all positive. The matrix
$Q$ is positive semidefinite provided $\ds \vecx^t Q \vecx \geq \zerovec$ for
all  $\vecx$ in $\R^n$ or if all eigenvalues of $Q$ are nonnegative. The terms
negative definite and negative semidefinite are defined analogously.

\section{Cramer's Rule}\label{S:CramersRule}\index{Cramer's Rule}

\noi
Suppose that $A$ is a square, $n$-by-$n$ matrix having a nonzero determinant. If
$\vecb$ belongs to $\R^n$ and if $\ds \vecx= \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}$,
then the solution to the system of equations $A\vecx=\vecb$ can be expressed as
\begin{equation*}
x_i = \frac{\det(A_i(\vecb))}{\det(A)},
\end{equation*}
where $1 \leq i \leq n$ and where $A_i(\vecb)$ denotes the matrix obtained by replacing column
$i$ of $A$ with the vector $\vecb$.

\section{The Rank-Nullity Theorem}\label{S:RankNullity}\index{Rank-Nullity Theorem}
\begin{theorem}\label{Th:RankNullityTheorem}
If $A$ is an $m$-by-$n$ matrix, then the dimension of the column space of $A$
added to the dimension of the null space of $A$ equals $n$.
\end{theorem}

\section{The Spectral Theorem}\label{S:SpectralTheorem}\index{Spectral Theorem}
\begin{theorem}\label{Th:SpectralTheorem}
Suppose $A$ is a symmetric matrix having real-valued entries. Then there exists an $n$-by-$n$ diagonal
matrix, $D$, and an $n$-by-$n$ matrix, $P$, having the property
that $\ds A=PDP^t$. The matrix $D$ can be chosen to have the eigenvalues of $A$ along
its diagonal. The matrix $P$ is then formed using as its columns the corresponding
eigenvectors of $A$, normalized so as to have length one. Finally, $P$ is invertible,
with $P^{-1}=P^t$.
\end{theorem}

\section{Matrix Norms}\label{S:MatrixNorms}\index{matrix norm}
\noi Let $M_n(\R)$ denote
the set of $n$-by-$n$ matrices having real-valued entries. Then $M_n(\R)$
forms a vector space under the usual operations of matrix addition and scalar multiplication. A norm
on $M_n(\R)$ is a function that assigns to each matrix, $A$, in this set, a nonnegative
real number,  $\ds \|A\|$. This function must satisfy the usual properties of a vector space norm:
\be
\item For each $A$ in $M_n(\R)$,  $\ds \|A\| \geq 0$, with equality possible only
if $A$ is the zero matrix.
\item For each $A$ in $M_n(\R)$ and each real scalar, $c$,  $\ds \|c A\| =|c|\|A\|$.
\item For every $A$ and $B$ in $M_n(\R)$,  $\ds \|A+B\| \leq \|A\|+\|B\|$.
\item For every $A$ and $B$ in $M_n(\R)$,  $\ds \|AB\| \leq \|A\|\|B\|$.
\ee

\noi
The third of these properties is referred to as the triangle inequality; the last is referred
to as the sub-multiplicative property and is analogous
to the Cauchy-Schwartz Inequality for vectors.

\newpar
While several different matrix norms exist for $M_n(\R)$, the one connects the Euclidean
norm of a vector, $\vecx$, in $\R^n$ with that of the matrix-product vector, $A\vecx$ is known
as the \emph{spectral norm}\index{spectral norm}. It is defined as
\begin{equation*}
\|A\|= \max \left\{ \sqrt{\lambda} \mid \lambda \mbox{ is an eigenvalue of } A^tA \right\}.
\end{equation*}
Note that by the last property from \ref{S:TransposeProperties}, each eigenvalue in this
set is nonnegative. The spectral norm of a matrix $A$ in $M_n(\R)$ satisfies the vector-norm
inequality
\begin{equation*}
\|A\vecx\| \leq \|A\| \|\vecx\| \mbox{ for all } \vecx \in \R^n.
\end{equation*}
In other words, multiplication of $\vecx$ by $A$ yields a vector whose length is no more than that
of $\vecx$, scaled by the matrix norm, $\|A\|$.

\newpar
When $A$ is symmetric, the eigenvalues of $AA^t$ are the eigenvalues of $A^2$, and the spectral norm
reduces to $\ds \|A\|=\rho(A)$, where $\rho(A)$ is the \emph{spectral radius}\index{spectral radius}, or maximum of the absolute values of the eigenvalues of $A$. Hence, for a symmetric matrix, $A$,
\begin{equation*}
\|A\vecx\| \leq \rho(A) \|\vecx\| \mbox{ for all } \vecx \in \R^n.
\end{equation*}


\endinput 