\documentclass[12pt]{article}
\input{../macros.tex}
\begin{document}

\thispagestyle{plain}

\setcounter{session}{24}
\begin{center}
\textbf{Exercises on Markov matrices; Fourier series}
\end{center}


\begin{problem} (6.4 \#7.  {\em Introduction to Linear Algebra:} Strang) 
\begin{enumerate}[a)]
\item Find a symmetric matrix $\twobytwo 1 b b 1$ that has a negative eigenvalue. 
\item How do you know it must have a negative pivot?

\item How do you know it can't have two negative eigenvalues?
\end{enumerate}
\end{problem}

\solution{
\begin{enumerate}[a)]
\item The eigenvalues of that matrix are $1 \pm b.$ If $b>1$ or $b < -1$ the matrix has a negative eigenvalue. 

\item The pivots have the same signs as the eigenvalues. If the matrix has a negative eigenvalue, then it must have a negative pivot.

\item 
To obtain one negative eigenvalue, we choose either $b>1$ or $b < -1$ (as stated in part (a)). If we choose $b>1,$ then $\lambda_1 = 1+b$ will be positive while $\lambda_2 = 1-b$ will be negative. Alternatively, if we choose $b<-1,$ then $\lambda_1 = 1+b$ will be negative while $\lambda_2 = 1-b$ will be positive. Therefore this matrix cannot have two negative eigenvalues.  
\end{enumerate}
}

\begin{problem} (6.4 \#23.) Which of these classes of matrices do $A$ and $B$ belong to: invertible, orthogonal, projection, permutation, diagonalizable, Markov?
$$A = \threebythree 0 0 1 0 1 0 1 0 0 \hspace{10pt} B =
  \frac{1}{3}\threebythree 1 1 1 1 1 1 1 1 1 .$$ Which of these
  factorizations are possible for $A$ and $B$: $LU$, $QR$, $S\Lambda
  S^{-1}$, or $Q\Lambda Q^{T}$?
\end{problem}

\solution{
\begin{enumerate}[a)]

\item For $A:$
\smallskip\\
\begin{tabular}{p{.58\textwidth}l}
$\det A = -1 \neq 0$. & $A$ is \textbf{invertible}.\\
$AA^T = I$. & $A$ is \textbf{orthogonal}.\\
$A^2 = I \neq A$. & $A$ is \textbf{not a projection}.\\
$A$ has one 1 in each row and column with 0's elsewhere. 
& $A$ is \textbf{a permutation}.\\
$A = A^T$, so $A$ is symmetric. & $A$ is \textbf{diagonalizable}.\\
Each column of $A$ sums to one. & A is \textbf{Markov}.\\
\end{tabular}
\smallskip\\
All of the factorizations are possible for $A$: $LU$ and $QR$ are always possible, $S \Lambda S^{-1}$ is possible because it is diagonalizable, and $Q \Lambda Q^T$ is possible because it is symmetric. 

\item For $B:$
\smallskip\\
\begin{tabular}{p{.58\textwidth}l}
$\det B = 0$. & $B$ is \textbf{not invertible}.\\
$BB^T \neq I$. & $B$ is \textbf{not orthogonal}.\\
$B^2 = B$. & $B$ is \textbf{a projection}.\\
$B$ does not have one 1 in each row and each column, with 0's elsewhere. & $B$ is \textbf{not a permutation}. \\
$B = B^T$ so $B$ is symmetric. & $B$ is \textbf{diagonalizable}.\\
Each column of $B$ sums to one. & $B$ is \textbf{Markov}.\\
\end{tabular}\smallskip\\
All of the factorizations are possible for $B$: $LU$ and $QR$ are always possible, $S \Lambda S^{-1}$ is possible because it is diagonalizable, and $Q \Lambda Q^T$ is possible because it is symmetric. 
\end{enumerate}
}

\begin{problem} (8.3 \#11.)  Complete $A$ to a Markov matrix and find the steady state eigenvector. When $A$ is a symmetric Markov matrix, why is $\vb x_1 = (1,\dots,1)$ its steady state?
$$A = \threebythree {.7} {.1} {.2} {.1} {.6} {.3} { \rule{5mm}{0.4pt}} { \rule{5mm}{0.4pt}} {\rule{5mm}{0.4pt}} . $$
\end{problem}

\solution{ Matrix $A$ becomes:
$$A = \threebythree {.7} {.1} {.2} {.1} {.6} {.3} {\mathbf{.2}} {\mathbf{.3}} {\mathbf{.5}},$$
with steady state vector (1,1,1). When $A$ is a \textit{symmetric} Markov matrix, the elements of each row sum to one. The elements of each row of $A-I$ then sum to zero. Since the steady state vector $\vb x$ is the eigenvector associated with eigenvalue $\lambda = 1,$ we solve $(A-\lambda I)\vb x = (A - I) \vb x= \vb 0$ to get $\vb x = (1,\dots,1).$ 
}

\end{document}