Practice Final Exam

Instructions:

You’ll have two hours to do the real exam. You’ll be asked to do it without notes or the computer, but you may use a calculator.

If you have any questions, or if you think there is a mistake in the question, please let me know.

1

A transition matrix A consists of only real entries. It has one real eigenvalue \(\lambda_1 = a_1\) and two complex eigenvalues \(\lambda_2 = a_2 + b_2 \text{i}, \lambda_3 = a_2 - b_2 \text{i}\), so that \(\lambda_2\) is the complex conjugate of \(\lambda_3\): \(\lambda_2=\overline{\lambda_3}\). It has corresponding eigenvectors \(\mathbf{v_1}, \mathbf{v_2}, \mathbf{v_3}\), where the entries in \(\mathbf{v_1}\) are real and the entries in \(\mathbf{v_2}\) are the complex conjugates of the entries of \(\mathbf{v_3}\).

(For matrices with all real entries, complex eigenvalues will always come in complex conjugate pairs, and their eigenvectors will always also be complex conguate pairs.)

  1. Suppose the initial population is given by \(\mathbf{x}=\begin{bmatrix} x_{1} \\ x_2 \\ x_3 \end{bmatrix}\), where \(x_1,x_2,x_3\) are real numbers. The projection of the initial population onto the eigenvectors is given by \(\mathbf{x}=c_1 \mathbf{v_1} + c_2 \mathbf{v_2} + c_3 \mathbf{v_3}\).

Using the fact that \(v_2\) and \(v_3\) are complex conjugates, show that \(c_2\) and \(c_3\) are also complex conjugates.

  1. In terms of the eigenvalues and eigenvectors, what will be the population distribution after \(k\) iterations?

  2. Using your results from the previous two parts, show that the population at time \(k\) will always have real entries.

(You may find it helpful to know that for complex scalars \(d,g\), \(\overline{dg}=\overline{d}\times\overline{g}\), and \(\overline{d^n}= \overline{d}^n\).)

  1. Argue that you could have gotten the same result as (c) but just using the fact that the matrix \(A\) has only real entries.

  2. Suppose \(|\lambda_1|>|\lambda_2|=|\lambda_3|\). Estimate \(\lim_{k\to\infty} \mathbf{x_k}\) for a random initial population \(\mathbf{x_0}\), for the cases where \(\lambda_1>1\), \(\lambda_1=1\), and \(\lambda_1<1\).

2

  1. Convert this difference equation into matrix–vector form.

\(y_{k+2} + y_{k+1} - 2y_{k} = 3\)

  1. Using the matrix, find \(y_2\) if it is given that \(y_0 = 2\) and \(y_1 = 2\).

3

A directed graph has vertices labeled \(A\), \(B\), \(C\), and \(D\). The edges are given by the following incidence matrix B:

\(\displaystyle B = \left[\begin{matrix}-1 & -1 & 0 & 0 & 0 & 1\\1 & 0 & -1 & -1 & 0 & 0\\0 & 1 & 1 & 0 & -1 & 0\\0 & 0 & 0 & 1 & 1 & -1\end{matrix}\right]\)

  1. Find the adjacency matrix \(A\) for the graph.

  2. Draw the graph.

  3. Describe how you could find the number of paths of length \(k\) between each pair of vertices using the adjacency matrix \(A\).

  4. If you calculate the matrix \(A\) + \(A^2\), what does the sum of the entries in the corresponding row tell you about the graph?

  5. Let \(\mathbf{v}\) be a row vector representing a subset of the edges in the graph. For example, the subset of edges given by the vector \(\mathbf{v} = [1, 0, 1, 0, 0, 1]\) would correspond to the first, third, and sixth edges.

    Write an equation which will be satisfied whenever the subset of edges represented by \(\mathbf{v}\) forms a loop in the graph.

  6. Describe two algorithms for ranking the importance of the vertices in a graph. (One or more of these algorithms may be based on prior parts of this problem.)

4

The system of equations

\[ \begin{aligned} x_{1}+x_{2} & =2 \\ x_{3}+x_{4} & =1 \\ 2 x_{1}+4 x_{2}+2 x_{4} & =6 \end{aligned} \]

has coefficient matrix \(A\) and right hand side \(\mathbf{b}\) such that the row-reduced echelon form of \([A \mid \mathbf{b}]\) is

\[ \left[\begin{array}{cccc|c}1 & 0 & 0 & -1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1\end{array}\right] \]

Use this information to answer the following:

  1. Find a basis for the null space of \(A\) (not \(A|b\)!).

  2. Find the form of a general solution of the system \(A \mathbf{x}=\mathbf{b}\).

  3. Find the rank of \(A\). Discuss the meaning of the rank in terms of the independence of the columns of \(A\).

5

You are given a matrix \(A\):

\(\displaystyle \left[\begin{matrix}0 & 1\\1 & 0\\1 & 1\end{matrix}\right]\)

The eigenvalues of \(AA^T\) are \(\lambda_1 = 3, \lambda_2 = 1, \lambda_3 = 0\).

  1. Find the eigenvalues of \(A^TA\).

  2. Using the facts below, find the eigenvectors of \(A^TA\) and \(AA^T\), and explain your reasoning.

  3. Find the singular value decomposition of \(A\).

  4. Using the SVD, calculate \(A^+\), the pseudoinverse of \(A\). Use this to solve the least squares problem \(A\mathbf{x} = \mathbf{b}\), where \(\mathbf{b} = [1, 4,2]^T\).

Here are some facts which may be helpful:

\(\displaystyle \left[\begin{matrix}1 & 0 & 1\\0 & 1 & 1\\1 & 1 & 2\end{matrix}\right]\left[\begin{matrix}-1\\-1\\1\end{matrix}\right]=\left[\begin{matrix}0\\0\\0\end{matrix}\right]\)

\(\displaystyle \left[\begin{matrix}-2 & 0 & 1\\0 & -2 & 1\\1 & 1 & -1\end{matrix}\right]\left[\begin{matrix}\frac{1}{2}\\\frac{1}{2}\\1\end{matrix}\right]=\left[\begin{matrix}0\\0\\0\end{matrix}\right]\)

\(\displaystyle \left[\begin{matrix}0 & 0 & 1\\0 & 0 & 1\\1 & 1 & 1\end{matrix}\right]\left[\begin{matrix}-1\\1\\0\end{matrix}\right]=\left[\begin{matrix}0\\0\\0\end{matrix}\right]\)

\(\displaystyle \left[\begin{matrix}1 & 1\\1 & 1\end{matrix}\right]\left[\begin{matrix}-1\\1\end{matrix}\right]=\left[\begin{matrix}0\\0\end{matrix}\right]\)

\(\displaystyle \left[\begin{matrix}-1 & 1\\1 & -1\end{matrix}\right]\left[\begin{matrix}1\\1\end{matrix}\right]=\left[\begin{matrix}0\\0\end{matrix}\right]\)

6

  1. For the matrix \(A = \begin{bmatrix} 9 & 8 \\ -6 & -5 \end{bmatrix}\), find the eigenvalues and eigenvectors.

  2. Using these results, find the matrix \(P\) such that \(P^{-1}AP\) is a diagonal matrix.

(Note: for a 2x2 matrix \(\begin{bmatrix}a&b\\c&d\end{bmatrix}\), you can calculate the inverse as \(\frac{1}{ad-bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\).)

  1. Diagonalize the matrix \(A^4+2A^2-3I\). (It’s fine to leave exponents in the answer, e.g. \(5^{6}\).)

  2. If \(A\mathbf v_i=\lambda_i\mathbf v_i\), note that \(\mathbf v_i\) is also an eigenvector of \(A^4+2A^2-3I\), and determine the corresponding eigenvalue.

Use this and the actual eigenvalues you found in part (a) to find the null space of \(A^4+2A^2-3I\).

7

The Discrete Fourier Transform (DFT) of a sequence \(x[n]\) is given by \(X[k] = \sum_{n=0}^{N-1} x[n] e^{-i2\pi kn/N}\), where \(N\) is the length of the sequence, and where \(k\) runs from \(0\) to \(N-1\). The inverse DFT is given by \(x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{i2\pi kn/N}\).

  1. Find the DFT of the filter \(h[n] = [\frac{1}{3},-\frac{1}{3},\frac{1}{3},0]\).

  2. Using this DFT, find the circular convolution of the sequences \(x[n] = [1,2,3,4]\) and \(h[n]\). Note: the DFT of \(x\) is \(X=[10,-2+2i,-2,-2-2i]\).

(Circular convolution is convolution where we assume the sequences are periodic, so that \(x[n] = x[n+N]\). It’s as if we had the long sequence \(x[n] = [\color{blue}1,2,3,4,\color{black}1,2,3,4,\color{blue}1,2,3,4,\ldots]\) to use when calculating the convolution. When we discussed convolution using the DFT in class, we were actually doing circular convolution. This matters if you want to check your results doing the convolution by hand without using the DFT.)

  1. From the plots below, match the signals to the correct DFTs. (Curve y3 is actually a quadratic. I have plotted only the absolute value of the DFTs. The complete DFT also includes negative frequencies, not shown here, which are the complex conjugates of the positive frequencies.)