Coordinates and Dimension, Digital Signal Processing, Difference Equations
Coordinate vectors · The dimension of a vector space and the Rank Theorem · Digital signal processing · Applications to difference equations
Days 1 to 3 are the lectures of Week 10; Day 4 is the single lecture of Week 11 (the week of the second midterm).
By the end of this week you will be able to:
- find the coordinate vector of a vector relative to a basis, and explain why a vector space with a basis of \(n\) vectors behaves like \(\mathbb R^n\);
- find the dimension of a subspace, and use the Rank Theorem to relate the rank, the nullity and the number of columns of a matrix;
- work with discrete-time signals, the shift transformation and moving averages, and decide whether a transformation of signals is linear time invariant;
- test signals for linear independence with the Casorati matrix, and solve a homogeneous linear difference equation with its auxiliary equation;
- write the general solution of a nonhomogeneous difference equation, and convert an \(n\text{th}\)-order equation into a first-order system \(\mathbf x_{k+1}=A\mathbf x_k\).
Day 1: Coordinate Systems; Dimension and Rank
Today a basis gives every vector a list of numbers, its coordinates, and we see that the number of vectors in a basis does not depend on which basis we choose. This number, the dimension, leads to the Rank Theorem.
- A basis for a vector space \(V\) (or for a subspace \(H\)) is a linearly independent set that spans \(V\) (or \(H\)).
- A set of \(n\) vectors in \(\mathbb R^n\) is a basis for \(\mathbb R^n\) exactly when the \(n\times n\) matrix with these columns is invertible, that is, when it has \(n\) pivot positions (equivalently, nonzero determinant).
- The pivot columns of \(A\) form a basis for \(\operatorname{Col} A\); the nonzero rows of an echelon form of \(A\) form a basis for \(\operatorname{Row} A\).
- Writing the general solution of \(A\mathbf x=\mathbf 0\) with the free variables as weights produces a linearly independent spanning set for \(\operatorname{Nul} A\), one vector for each free variable.
- A system with augmented matrix \([\,\mathbf v_1\ \cdots\ \mathbf v_p\mid\mathbf y\,]\) is solved by row reduction; the solution gives the weights that express \(\mathbf y\) as a combination of \(\mathbf v_1,\dots,\mathbf v_p\).
1.1 Coordinates relative to a basis
A basis is a spanning set that is linearly independent. The independence has a practical consequence: every vector can be built from the basis in exactly one way, so the weights can serve as the "address" of the vector.
Let \(\mathcal B=\{\mathbf b_1,\dots,\mathbf b_n\}\) be a basis for a vector space \(V\). Then for each \(\mathbf x\) in \(V\) there is exactly one list of scalars \(c_1,\dots,c_n\) such that
\[\mathbf x=c_1\mathbf b_1+\cdots+c_n\mathbf b_n.\]Suppose \(\mathcal B=\{\mathbf b_1,\dots,\mathbf b_n\}\) is a basis for \(V\) and \(\mathbf x\) is in \(V\). The coordinates of \(\mathbf x\) relative to \(\mathcal B\) are the weights \(c_1,\dots,c_n\) with \(\mathbf x=c_1\mathbf b_1+\cdots+c_n\mathbf b_n\), and the vector in \(\mathbb R^n\)
\[[\,\mathbf x\,]_{\mathcal B}=\begin{bmatrix} c_1\\ \vdots\\ c_n\end{bmatrix}\]is the coordinate vector of \(\mathbf x\) relative to \(\mathcal B\). The mapping \(\mathbf x\mapsto[\,\mathbf x\,]_{\mathcal B}\) is the coordinate mapping determined by \(\mathcal B\). The order of the vectors in \(\mathcal B\) matters: it fixes which weight comes first.
Let \(\mathcal B=\{\mathbf b_1,\mathbf b_2\}\) with \(\mathbf b_1=\begin{bmatrix} 1\\ 0\end{bmatrix}\), \(\mathbf b_2=\begin{bmatrix} 1\\ 2\end{bmatrix}\), a basis for \(\mathbb R^2\).
Solution
Let \(\mathcal B=\{\mathbf b_1,\dots,\mathbf b_n\}\) be a basis for a vector space \(V\). Then the coordinate mapping \(\mathbf x\mapsto[\,\mathbf x\,]_{\mathcal B}\) is a one-to-one linear transformation from \(V\) onto \(\mathbb R^n\).
A one-to-one linear transformation from a vector space \(V\) onto a vector space \(W\) is called an isomorphism. Two isomorphic spaces may look different, but every vector space calculation in one is reproduced exactly in the other: sums go to sums, scalar multiples to scalar multiples, and distinct vectors to distinct vectors. Theorem 9 says that any vector space with a basis of \(n\) vectors is a copy of \(\mathbb R^n\). On Day 2 this is how a recording of \(n+1\) samples becomes a vector in \(\mathbb R^{n+1}\).
Self-check only. These exercises are not graded. Entries may be typed as integers, decimals (1.5 or 1,5) or simple fractions (3/2).
1.2 The dimension of a vector space
A vector space can have many bases. The next two theorems show that all of them have the same size.
Theorem 10. If \(V\) has a basis \(\mathcal B=\{\mathbf b_1,\dots,\mathbf b_n\}\), then any set in \(V\) with more than \(n\) vectors is linearly dependent.
Theorem 11. If \(V\) has a basis of \(n\) vectors, then every basis of \(V\) consists of exactly \(n\) vectors.
If a vector space \(V\) is spanned by a finite set, then \(V\) is finite-dimensional, and the dimension of \(V\), written \(\dim V\), is the number of vectors in a basis for \(V\). The dimension of the zero space \(\{\mathbf 0\}\) is defined to be \(0\). If \(V\) is not spanned by any finite set, \(V\) is infinite-dimensional.
Find the dimension of \(H=\{(a-b,\ 2a+2c,\ b+c,\ a+c): a,b,c \text{ real}\}\), a subspace of \(\mathbb R^4\).
Solution
Split a typical vector by the parameters:
\[\begin{bmatrix} a-b\\ 2a+2c\\ b+c\\ a+c\end{bmatrix}=a\begin{bmatrix} 1\\ 2\\ 0\\ 1\end{bmatrix}+b\begin{bmatrix} -1\\ 0\\ 1\\ 0\end{bmatrix}+c\begin{bmatrix} 0\\ 2\\ 1\\ 1\end{bmatrix}=a\mathbf v_1+b\mathbf v_2+c\mathbf v_3.\]So \(H=\operatorname{Span}\{\mathbf v_1,\mathbf v_2,\mathbf v_3\}\). Now \(\mathbf v_1\neq\mathbf 0\), and \(\mathbf v_2\) is not a multiple of \(\mathbf v_1\), so \(\{\mathbf v_1,\mathbf v_2\}\) is linearly independent. But \(\mathbf v_3=\mathbf v_1+\mathbf v_2\): the sum of \((1,2,0,1)\) and \((-1,0,1,0)\) is \((0,2,1,1)\). By the Spanning Set Theorem we may discard \(\mathbf v_3\) and still span \(H\). Hence \(\{\mathbf v_1,\mathbf v_2\}\) is a basis for \(H\) and \(\dim H=2\). Geometrically, \(H\) is a plane through the origin in \(\mathbb R^4\), even though it was described with three parameters.
Let \(H\) be a subspace of a finite-dimensional vector space \(V\). Any linearly independent set in \(H\) can be expanded, if necessary, to a basis for \(H\). Also, \(H\) is finite-dimensional and
\[\dim H\le\dim V.\]Let \(V\) be a \(p\)-dimensional vector space, \(p\ge 1\). Any linearly independent set of exactly \(p\) vectors in \(V\) is automatically a basis for \(V\). Any set of exactly \(p\) vectors that spans \(V\) is automatically a basis for \(V\).
When the dimension is known, only one of the two basis properties has to be checked. Independence is usually the easier one. We will use this on Day 3, where the solution space of a difference equation has a known dimension.
Self-check only. Several bases are correct; the check tests whether your vectors lie in \(W\), are independent, and are the right number.
Let \(W=\operatorname{Span}\{(1,0,2),\ (3,1,1),\ (9,4,-2),\ (-7,-3,1)\}\) in \(\mathbb R^3\). Find \(\dim W\) and a basis for \(W\). Enter the basis vectors as the columns of the grid; leave a column empty if your basis has fewer vectors.
Put the vectors into the columns of a matrix and row reduce. \(R_3\to R_3-2R_1\) gives row \((0,-5,-20,15)\); then \(R_3\to R_3+5R_2\) gives a zero row:
\[\begin{bmatrix} 1 & 3 & 9 & -7\\ 0 & 1 & 4 & -3\\ 2 & 1 & -2 & 1\end{bmatrix}\sim\begin{bmatrix} 1 & 3 & 9 & -7\\ 0 & 1 & 4 & -3\\ 0 & 0 & 0 & 0\end{bmatrix}.\]Two pivot columns, so \(\dim W=2\), and the pivot columns of the original matrix, \((1,0,2)\) and \((3,1,1)\), form a basis. \(W\) is a plane through the origin. Any two vectors of \(W\) that are not multiples of each other also form a basis, for example \((9,4,-2)\) and \((-7,-3,1)\).
1.3 Rank and the Rank Theorem
The dimensions of the subspaces attached to a matrix have their own names, and they are connected by one short equation.
The rank of an \(m\times n\) matrix \(A\) is the dimension of its column space, \(\operatorname{rank} A=\dim\operatorname{Col} A\). The nullity of \(A\) is the dimension of its null space, \(\operatorname{nullity} A=\dim\operatorname{Nul} A\).
- \(\operatorname{rank} A\) is the number of pivot columns, because the pivot columns of \(A\) form a basis for \(\operatorname{Col} A\).
- \(\dim\operatorname{Row} A\) is the number of nonzero rows of an echelon form, which is the number of pivots. So \(\dim\operatorname{Row} A=\operatorname{rank} A\) as well.
- \(\operatorname{nullity} A\) is the number of free variables in \(A\mathbf x=\mathbf 0\), because the usual method produces one basis vector of \(\operatorname{Nul} A\) for each free variable.
For an \(m\times n\) matrix \(A\),
\[\operatorname{rank} A+\operatorname{nullity} A=n,\ \text{the number of columns of } A.\]Find the rank and the nullity of \(A=\begin{bmatrix} 1 & 2 & 0 & -1 & 3\\ 2 & 4 & 1 & 0 & 5\\ -1 & -2 & 1 & 3 & -4\end{bmatrix}\).
Solution
Row reduce. \(R_2\to R_2-2R_1\) gives \((0,0,1,2,-1)\) and \(R_3\to R_3+R_1\) gives \((0,0,1,2,-1)\) as well; then \(R_3\to R_3-R_2\) produces a zero row:
\[A\sim\begin{bmatrix} 1 & 2 & 0 & -1 & 3\\ 0 & 0 & 1 & 2 & -1\\ 0 & 0 & 0 & 0 & 0\end{bmatrix}.\]This echelon form is already reduced. Pivots are in columns 1 and 3, so \(\operatorname{rank} A=2\). The free variables are \(x_2,x_4,x_5\), so \(\operatorname{nullity} A=3\). Check: \(2+3=5\), the number of columns.
The pivot columns of \(A\) give a basis for \(\operatorname{Col} A\) (two vectors), the nonzero rows of the echelon form give a basis for \(\operatorname{Row} A\) (two vectors), and the three free variables give three basis vectors for \(\operatorname{Nul} A\), as the nullity predicts.
Solution
Self-check only.
Day 2: Digital Signal Processing
Today a sequence of measurements is a vector. We create new signals from one signal with the shift transformation, and we smooth data with moving averages.
- The space \(\mathbb S\) of signals consists of all doubly infinite sequences \(\{y_k\}=(\dots,y_{-1},y_0,y_1,\dots)\), with term-by-term addition and scaling: \(\{y_k\}+\{z_k\}=\{y_k+z_k\}\), \(c\{y_k\}=\{cy_k\}\). The zero signal has every entry \(0\).
- A transformation \(T:\mathbb S\to\mathbb S\) is linear when \(T(\mathbf x+\mathbf y)=T(\mathbf x)+T(\mathbf y)\) and \(T(c\mathbf x)=cT(\mathbf x)\) for all signals \(\mathbf x,\mathbf y\) and scalars \(c\). Its kernel is the set of signals sent to the zero signal; the kernel is a subspace of \(\mathbb S\).
- The two-day moving average \(M_2(\{p_k\})=\{(p_k+p_{k-1})/2\}\) is linear, and its kernel consists of the multiples of the alternating signal \(\{(-1)^k\}\).
- A basis for a vector space is a linearly independent set that spans it; the dimension is the number of vectors in a basis.
2.1 Discrete-time signals
A signal records a quantity at equally spaced times: a sound pressure \(44\,100\) times per second, a stock price once a day, a temperature once an hour. The index \(k\) is the time step, and \(y_k\) is the value recorded at step \(k\). We allow all integers \(k\), negative ones included, so that a signal has no beginning and no end; a measurement that starts at time \(0\) is a signal with \(y_k=0\) for \(k<0\). Table 1 lists the signals we will use most, and Figure 2 plots four of them.
| Name | Symbol | Entries | Formal description |
|---|---|---|---|
| delta | \(\delta\) | \((\dots,0,0,\underline{1},0,0,\dots)\) | \(d_k=1\) if \(k=0\), \(d_k=0\) if \(k\neq 0\) |
| unit step | \(\upsilon\) | \((\dots,0,0,\underline{1},1,1,\dots)\) | \(u_k=1\) if \(k\ge 0\), \(u_k=0\) if \(k<0\) |
| constant | \(\chi\) | \((\dots,1,1,\underline{1},1,1,\dots)\) | \(c_k=1\) for all \(k\) |
| alternating | \(\alpha\) | \((\dots,1,-1,\underline{1},-1,1,\dots)\) | \(a_k=(-1)^k\) |
| Fibonacci | \(F\) | \((\dots,2,-1,1,\underline{0},1,1,2,3,\dots)\) | \(f_0=0\), \(f_1=1\), \(f_k=f_{k-1}+f_{k-2}\) for \(k>1\), \(f_k=f_{k+2}-f_{k+1}\) for \(k<0\) |
| exponential | \(\epsilon_c\) | \((\dots,c^{-2},c^{-1},\underline{1},c,c^2,\dots)\) | \(e_k=c^k\), for a fixed \(c\neq 0\) |
A signal \(\{p_k\}\) is periodic if there is a positive integer \(q\) with \(p_{k+q}=p_k\) for all \(k\). The alternating signal is periodic with \(q=2\). The sinusoidal signals \(\{\cos(fk\pi+\theta\pi)\}\), with fixed rational numbers \(f\) and \(\theta\), are periodic; sampling a sound or a voltage produces signals of this kind, and we meet them again on Day 3.
Find \(\chi+\alpha\) and \(\upsilon-\alpha\). Give each answer as a list of entries and as a formal description.
Solution
Add entry by entry, keeping the positions aligned:
\[\begin{array}{rcl} \chi & = & (\dots,1,1,1,\underline{1},1,1,1,\dots)\\ \alpha & = & (\dots,-1,1,-1,\underline{1},-1,1,-1,\dots)\\ \hline \chi+\alpha & = & (\dots,0,2,0,\underline{2},0,2,0,\dots)\end{array}\]Formal description: the \(k\text{th}\) entry is \(1+(-1)^k\), which is \(2\) when \(k\) is even and \(0\) when \(k\) is odd.
For \(\upsilon-\alpha\), the \(k\text{th}\) entry is \(u_k-(-1)^k\). For \(k\ge 0\) this is \(1-(-1)^k\): \(0\) for even \(k\), \(2\) for odd \(k\). For \(k<0\) it is \(0-(-1)^k\): \(-1\) for even \(k\), \(1\) for odd \(k\). So
\[\upsilon-\alpha=(\dots,1,-1,1,\underline{0},2,0,2,0,\dots).\]Self-check only. Enter the six entries of each signal for \(k=-2,-1,0,1,2,3\).
2.2 The shift transformation and linear time invariance
In \(\mathbb R^n\), the standard basis vectors \(\mathbf e_1,\dots,\mathbf e_n\) each have a single entry \(1\). In \(\mathbb S\), the signal \(\delta\) has a single entry \(1\), at \(k=0\). Instead of storing one such signal for every position, a processor creates them from \(\delta\) by shifting.
Let \(S\) be the transformation that moves every entry of a signal one step to the right:
\[S(\{x_k\})=\{x_{k-1}\},\]that is, the entry of \(S(\mathbf x)\) at position \(k\) is the entry of \(\mathbf x\) at position \(k-1\). Figure 3 shows a signal and its shift. The opposite move is \(S^{-1}(\{x_k\})=\{x_{k+1}\}\), and \(S^{-1}S=SS^{-1}=I\), the identity transformation: shifting right and then left changes nothing. Applying \(S\) repeatedly to \(\delta\) moves its single \(1\) along the index line:
\[\begin{array}{lcl} S^{-1}(\delta) & = & (\dots,0,1,\underline{0},0,0,\dots)\\ \delta & = & (\dots,0,0,\underline{1},0,0,\dots)\\ S(\delta) & = & (\dots,0,0,\underline{0},1,0,\dots)\\ S^{2}(\delta) & = & (\dots,0,0,\underline{0},0,1,\dots)\end{array}\]In general \(S^j(\delta)\) has its \(1\) at position \(k=j\) and zeros elsewhere, for every integer \(j\).
The shift is linear: \(S(\{x_k\}+\{y_k\})=\{x_{k-1}+y_{k-1}\}=S(\{x_k\})+S(\{y_k\})\) and \(S(c\{x_k\})=\{cx_{k-1}\}=cS(\{x_k\})\). It has one more property: it does not care when a signal arrives. If the input is delayed by \(q\) steps, the output is delayed by the same \(q\) steps. Transformations with this property are the ones a signal processor can implement with a fixed circuit or a fixed program.
A transformation \(T:\mathbb S\to\mathbb S\) is linear time invariant (LTI) if
Property (iii) is time invariance: shifting the input by \(q\) steps shifts the output by \(q\) steps.
Properties (i) and (ii) are exactly the two properties of a linear transformation. So every linear time invariant transformation on \(\mathbb S\) is a linear transformation, and everything we know about linear transformations applies: its kernel and its range are subspaces of \(\mathbb S\).
Let \(T(\{x_k\})=\{x_k-x_{k-1}\}\): each output entry is the change from the previous input entry to the current one. Show that \(T\) is LTI and find its kernel.
Solution
So \(T\) is LTI. A signal is in the kernel when \(x_k-x_{k-1}=0\) for every \(k\), that is, \(x_k=x_{k-1}\) for all \(k\). Starting from \(x_0\) and moving in both directions, every entry equals \(x_0\). The kernel is the set of constant signals, the multiples \(x_0\chi\) of the constant signal \(\chi\). This matches what the transformation measures: a signal that never changes has zero differences. In the notation of the shift, \(T=I-S\).
Self-check only.
For each transformation \(T:\mathbb S\to\mathbb S\), choose the correct description.
2.3 Moving averages: smoothing a signal
LTI transformations create signals, as the shift does, and they also filter signals. The two-day moving average replaces each value by the average of the current and the previous value. Averaging over more steps smooths more strongly.
For a positive integer \(m\), the moving average transformation \(M_m:\mathbb S\to\mathbb S\) is
\[M_m(\{x_k\})=\{y_k\}\quad\text{where}\quad y_k=\frac1m\sum_{j=k-m+1}^{k}x_j=\frac{x_{k-m+1}+\cdots+x_{k-1}+x_k}{m}.\]Each output value is the average of the last \(m\) input values. For \(m=2\) this is \(M_2\); for \(m=3\), \(y_k=\tfrac13(x_{k-2}+x_{k-1}+x_k)\). Since \(M_m=\tfrac1m\,(I+S+S^2+\cdots+S^{m-1})\) is a combination of shifts, \(M_m\) is LTI.
A quantity is measured at \(k=0,1,\dots,12\): \(4,6,3,7,5,8,6,9,7,10,8,11,9\) (and the signal is \(0\) outside this range). Compute \(M_3\) of this signal for \(k=2,\dots,12\).
Solution
Each output is the average of three consecutive inputs ending at \(k\):
\[y_2=\frac{4+6+3}{3}=\frac{13}{3},\quad y_3=\frac{6+3+7}{3}=\frac{16}{3},\quad y_4=\frac{3+7+5}{3}=5,\] \[y_5=\frac{7+5+8}{3}=\frac{20}{3},\quad y_6=\frac{5+8+6}{3}=\frac{19}{3},\quad y_7=\frac{8+6+9}{3}=\frac{23}{3},\] \[y_8=\frac{22}{3},\quad y_9=\frac{26}{3},\quad y_{10}=\frac{25}{3},\quad y_{11}=\frac{29}{3},\quad y_{12}=\frac{28}{3}.\]Figure 4 shows the input and the output. The input jumps up and down at every step; the output rises steadily. The moving average removed the step-to-step oscillation and kept the trend. Note that the output lags behind: \(y_k\) uses values up to time \(k\) only, so a processor can compute it in real time.
Find the kernel of \(M_3\).
Solution
\(\{x_k\}\) is in the kernel when \(x_{k-2}+x_{k-1}+x_k=0\) for every \(k\), that is, \(x_k=-x_{k-1}-x_{k-2}\). Every entry is determined by the two before it (and, reading the relation as \(x_{k-2}=-x_k-x_{k-1}\), by the two after it). So a signal in the kernel is fixed by \(x_0\) and \(x_1\). Take \(x_0=a\), \(x_1=b\): then \(x_2=-a-b\), \(x_3=-b-(-a-b)=a\), \(x_4=b\), and the pattern repeats with period \(3\); the same happens to the left. So
\[\ker M_3=\{(\dots,a,b,-a-b,\underline{a},b,-a-b,a,\dots): a,b\text{ real}\},\]the signals of period \(3\) whose three values add up to \(0\). For \(a=1,b=0\) and for \(a=0,b=1\) we get the two signals
\[\mathbf w_1=(\dots,1,0,-1,\underline{1},0,-1,1,\dots),\qquad \mathbf w_2=(\dots,0,1,-1,\underline{0},1,-1,0,\dots),\]and every signal in the kernel is \(a\mathbf w_1+b\mathbf w_2\). They are not multiples of each other, so \(\{\mathbf w_1,\mathbf w_2\}\) is a basis for \(\ker M_3\) and \(\dim\ker M_3=2\). These are exactly the patterns that a three-term average cannot see. Compare with \(M_2\), whose kernel is the line spanned by the alternating signal.
Day 3: Finite Signals, Independence of Signals, and Filters
Today we find bases for the signals of finite length, test signals for linear independence with the Casorati matrix, and see that a linear difference equation is the same thing as an LTI filter.
- The shift \(S(\{x_k\})=\{x_{k-1}\}\) moves a signal one step to the right; \(S^j(\delta)\) has a single entry \(1\), at position \(k=j\). The shift and its combinations are linear time invariant.
- A basis for a vector space is a linearly independent spanning set; the dimension is the number of vectors in a basis. A one-to-one linear transformation of \(V\) onto \(\mathbb R^n\) is an isomorphism: \(V\) behaves exactly like \(\mathbb R^n\).
- Signals \(\mathbf u,\mathbf v,\mathbf w\) are linearly independent when \(c_1\mathbf u+c_2\mathbf v+c_3\mathbf w=\mathbf 0\) (the zero signal) forces \(c_1=c_2=c_3=0\). Two signals are dependent exactly when one is a multiple of the other.
- For a \(3\times 3\) matrix, \(\det\begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i\end{bmatrix}=a(ei-fh)-b(di-fg)+c(dh-eg)\). A square matrix is invertible exactly when its determinant is not \(0\), and then \(A\mathbf c=\mathbf 0\) has only the solution \(\mathbf c=\mathbf 0\).
- The kernel of a linear transformation \(T:\mathbb S\to\mathbb S\) is a subspace of \(\mathbb S\).
3.1 Bases for subspaces of \(\mathbb S\)
Data recorded over a fixed number of time steps lives in a small subspace of \(\mathbb S\), and the shift of \(\delta\) provides a basis for it.
For \(n\ge 0\), the set \(\mathbb S_n\) of signals of length \(n\) consists of all signals \(\{y_k\}\) with \(y_k=0\) whenever \(k<0\) or \(k>n\). A signal in \(\mathbb S_n\) has \(n+1\) possibly nonzero entries, \(y_0,\dots,y_n\). For example, \((\dots,0,\underline{5},0,-2,1,0,\dots)\) is in \(\mathbb S_3\), and it equals \(5\delta-2S^2(\delta)+S^3(\delta)\).
\(\mathbb S_n\) is a subspace of \(\mathbb S\), and \(\mathcal B_n=\{\delta,\ S(\delta),\ S^2(\delta),\ \dots,\ S^n(\delta)\}\) is a basis for \(\mathbb S_n\). Hence \(\dim\mathbb S_n=n+1\) and \(\mathbb S_n\) is isomorphic to \(\mathbb R^{n+1}\).
The set \(\mathbb S_f\) of finitely supported signals consists of the signals \(\{y_k\}\) with only finitely many nonzero entries. Every \(\mathbb S_n\) is contained in \(\mathbb S_f\), and \(\mathbb S_f\) is a subspace of \(\mathbb S\). For example, \(\delta+3S^{5}(\delta)-S^{-2}(\delta)\) is in \(\mathbb S_f\) but in no \(\mathbb S_n\) (it has a nonzero entry at \(k=-2\)), and the unit step \(\upsilon\) is not in \(\mathbb S_f\).
The set \(\mathcal B_f=\{S^j(\delta): j \text{ an integer}\}\) is a basis for \(\mathbb S_f\), and \(\mathbb S_f\) is infinite-dimensional.
The unit step satisfies \(\upsilon=\delta+S(\delta)+S^2(\delta)+\cdots\), but a linear combination has finitely many terms, so \(\upsilon\) is not in \(\mathbb S_f\), and the shifted deltas are not a basis for all of \(\mathbb S\). Signals with infinite support, such as \(\upsilon\), \(\alpha\) and the exponential and sinusoidal signals, are described by difference equations, which we meet in 3.3 and solve on Day 4.
Self-check only. In (b) many answers are possible; the check computes with your entries.
3.2 Linear independence in the space of signals
Three signals \(\{u_k\},\{v_k\},\{w_k\}\) are linearly independent exactly when
\[c_1u_k+c_2v_k+c_3w_k=0\quad\text{for all } k \tag{1}\]implies \(c_1=c_2=c_3=0\). "For all \(k\)" means for every integer \(k\), so (1) holds in particular at any three consecutive times \(k\), \(k+1\), \(k+2\). Written as a matrix equation, the three statements say
\[\begin{bmatrix} u_k & v_k & w_k\\ u_{k+1} & v_{k+1} & w_{k+1}\\ u_{k+2} & v_{k+2} & w_{k+2}\end{bmatrix}\begin{bmatrix} c_1\\ c_2\\ c_3\end{bmatrix}=\begin{bmatrix} 0\\ 0\\ 0\end{bmatrix}\quad\text{for all } k. \tag{2}\]The coefficient matrix in (2) is the Casorati matrix \(C(k)\) of the signals; its determinant is their Casoratian. (For \(n\) signals the Casorati matrix is \(n\times n\), with rows at times \(k,k+1,\dots,k+n-1\).)
If the Casorati matrix \(C(k)\) is invertible for at least one value of \(k\), then (2) forces \(c_1=c_2=c_3=0\), so the signals are linearly independent.
If \(C(k)\) is not invertible for the chosen \(k\), the test is inconclusive in general. But when the signals are all solutions of the same homogeneous difference equation, as in 3.3, there is no ambiguity: either \(C(k)\) is invertible for every \(k\) and the signals are independent, or \(C(k)\) is singular for every \(k\) and the signals are dependent.
Show that \(\{2^k\}\), \(\{(-1)^k\}\) and \(\{3^k\}\) are linearly independent.
Solution
The Casorati matrix is
\[C(k)=\begin{bmatrix} 2^k & (-1)^k & 3^k\\ 2^{k+1} & (-1)^{k+1} & 3^{k+1}\\ 2^{k+2} & (-1)^{k+2} & 3^{k+2}\end{bmatrix}.\]It is enough to check one value of \(k\). Take \(k=0\) and compute the determinant by expansion across the first row:
\[\det C(0)=\det\begin{bmatrix} 1 & 1 & 1\\ 2 & -1 & 3\\ 4 & 1 & 9\end{bmatrix}=1\,(-9-3)-1\,(18-12)+1\,(2+4)=-12-6+6=-12\neq 0.\]So \(C(0)\) is invertible and the three signals are linearly independent. We will meet these three signals again on Day 4, as solutions of one difference equation.
Self-check only.
3.3 Linear difference equations and LTI filters
Given scalars \(a_0,\dots,a_n\) with \(a_0\neq 0\) and \(a_n\neq 0\), and a signal \(\{z_k\}\), the equation
\[a_0y_{k+n}+a_1y_{k+n-1}+\cdots+a_{n-1}y_{k+1}+a_ny_k=z_k\quad\text{for all } k \tag{3}\]is a linear difference equation of order \(n\). Usually \(a_0=1\). If \(\{z_k\}\) is the zero signal, the equation is homogeneous; otherwise it is nonhomogeneous. A signal \(\{y_k\}\) that satisfies (3) for every \(k\) is a solution.
In digital signal processing, equation (3) describes a linear time invariant filter with filter coefficients \(a_0,\dots,a_n\). The input is \(\{y_k\}\) and the output is \(\{z_k\}\). In the notation of the shift,
\[T=a_0S^{-n}+a_1S^{-n+1}+\cdots+a_{n-1}S^{-1}+a_nS^0,\qquad T(\{y_k\})=\{z_k\},\]a combination of shifts, hence an LTI transformation. The solution set of the homogeneous equation is the kernel of \(T\): the signals that the filter removes.
Consider the filter
\[z_k=\tfrac14\,(y_k+2y_{k+1}+y_{k+2}),\]a weighted average of three consecutive input values, the middle one counted twice. Feed in the signal \(y_k=\cos(\pi k/2)\), which repeats every \(4\) steps:
\[\{y_k\}=(\dots,\underline{1},\ 0,\ -1,\ 0,\ 1,\ 0,\ -1,\ 0,\dots).\]Solution
Compute each output from three consecutive inputs:
| \(k\) | \(y_k\) | \(y_{k+1}\) | \(y_{k+2}\) | \(\tfrac14(y_k+2y_{k+1}+y_{k+2})=z_k\) |
|---|---|---|---|---|
| 0 | 1 | 0 | \(-1\) | \(\tfrac14(1+0-1)=0\) |
| 1 | 0 | \(-1\) | 0 | \(\tfrac14(0-2+0)=-\tfrac12\) |
| 2 | \(-1\) | 0 | 1 | \(\tfrac14(-1+0+1)=0\) |
| 3 | 0 | 1 | 0 | \(\tfrac14(0+2+0)=\tfrac12\) |
| 4 | 1 | 0 | \(-1\) | \(\tfrac14(1+0-1)=0\) |
| 5 | 0 | \(-1\) | 0 | \(\tfrac14(0-2+0)=-\tfrac12\) |
The output is \((\dots,\underline{0},\ -\tfrac12,\ 0,\ \tfrac12,\ 0,\ -\tfrac12,\dots)\), that is, \(z_k=\tfrac12\,y_{k+1}\): the same oscillation, one step earlier and with half the amplitude. The filter lets this signal through, weakened.
Now feed in the alternating signal \(\alpha\), \(w_k=(-1)^k\), the fastest oscillation a signal can have: \((\dots,\underline{1},-1,1,-1,\dots)\). Three consecutive entries are always \(1,-1,1\) or \(-1,1,-1\), so
\[z_k=\tfrac14\,(w_k+2w_{k+1}+w_{k+2})=\tfrac14\,(-1)^k(1-2+1)=0\quad\text{for every } k.\]The output is the zero signal (Figure 5): the filter stops the fast signal completely. At the other extreme, the constant signal \(\chi\) passes unchanged, since \(\tfrac14(1+2+1)=1\). Slow signals pass and fast ones are removed; a filter with this behavior is a low-pass filter. The signal \(\alpha\) is in the kernel of the filter: it is a solution of the homogeneous equation \(y_{k+2}+2y_{k+1}+y_k=0\).
Self-check only.
The filter \(z_k=y_{k+2}-2y_{k+1}+y_k\) computes the second difference of its input. Compute \(z_0,z_1,z_2\) for each input.
Day 4: Solving Linear Difference Equations
Today we solve homogeneous linear difference equations with the auxiliary equation, fit a solution to given initial values, handle a nonhomogeneous equation with a particular solution, and turn an \(n\)th-order equation into a first-order system.
- A linear difference equation of order \(n\) is \(y_{k+n}+a_1y_{k+n-1}+\cdots+a_{n-1}y_{k+1}+a_ny_k=z_k\) for all \(k\), with \(a_n\neq 0\); it is homogeneous when \(\{z_k\}\) is the zero signal. A signal that satisfies it for every \(k\) is a solution. The equation describes the LTI filter \(T=S^{-n}+a_1S^{-n+1}+\cdots+a_nS^0\), and the solutions of the homogeneous equation form the kernel of \(T\), a subspace of \(\mathbb S\).
- Casorati test: signals are linearly independent if their Casorati matrix \(C(k)\) is invertible for one \(k\). For \(\{2^k\},\{(-1)^k\},\{3^k\}\), \(\det C(0)=-12\neq 0\), so these three signals are linearly independent.
- Basis Theorem: in a vector space of dimension \(p\), any \(p\) linearly independent vectors form a basis.
- A quadratic \(r^2+ar+b=0\) has roots \(r=\frac{-a\pm\sqrt{a^2-4b}}{2}\); when \(a^2-4b<0\) the roots are the complex numbers \(s(\cos\omega\pm i\sin\omega)\) with \(s=\sqrt b\).
- Two signals are linearly dependent exactly when one is a multiple of the other.
4.1 Solving homogeneous difference equations
Solutions of a homogeneous equation often have the form \(\{r^k\}\) for some number \(r\). Substituting this form turns the difference equation into a polynomial equation.
Find solutions of the form \(\{r^k\}\) of
\[y_{k+3}-4y_{k+2}+y_{k+1}+6y_k=0\quad\text{for all } k. \tag{4}\]Solution
Substitute \(y_k=r^k\), with \(r\neq 0\), and factor out \(r^k\):
\[r^{k+3}-4r^{k+2}+r^{k+1}+6r^k=r^k\,(r^3-4r^2+r+6)=0.\]Since \(r^k\neq 0\), \(\{r^k\}\) is a solution exactly when \(r^3-4r^2+r+6=0\). Try small integers: \(r=2\) gives \(8-16+2+6=0\), so \(r-2\) is a factor, and \(r^3-4r^2+r+6=(r-2)(r^2-2r-3)=(r-2)(r+1)(r-3)\). The roots are \(2,-1,3\), so \(\{2^k\}\), \(\{(-1)^k\}\) and \(\{3^k\}\) are solutions of (4). Check for \(3^k\): \(3^{k+3}-4\cdot 3^{k+2}+3^{k+1}+6\cdot 3^k=3^k(27-36+3+6)=0\).
A nonzero signal \(\{r^k\}\) satisfies the homogeneous equation
\[y_{k+n}+a_1y_{k+n-1}+\cdots+a_{n-1}y_{k+1}+a_ny_k=0\quad\text{for all } k\]if and only if \(r\) is a root of the auxiliary equation
\[r^n+a_1r^{n-1}+\cdots+a_{n-1}r+a_n=0.\]When the auxiliary equation has a complex root \(s(\cos\omega+i\sin\omega)\), the difference equation has the two real solutions \(\{s^k\cos k\omega\}\) and \(\{s^k\sin k\omega\}\). (A repeated root is not treated in this course.)
Find two solutions of \(y_{k+2}+4y_k=0\).
Solution
The auxiliary equation \(r^2+4=0\) has the roots \(r=\pm 2i=2(\cos\tfrac{\pi}{2}\pm i\sin\tfrac{\pi}{2})\), so \(s=2\) and \(\omega=\pi/2\). Two solutions are
\[\{2^k\cos\tfrac{k\pi}{2}\}=(\underline{1},0,-4,0,16,0,-64,\dots),\qquad \{2^k\sin\tfrac{k\pi}{2}\}=(\underline{0},2,0,-8,0,32,0,\dots)\](entries for \(k=0,1,2,\dots\)). Check the first one: every entry two steps later is \(-4\) times the current entry, so \(y_{k+2}+4y_k=0\). The solutions oscillate with period \(4\) and grow by the factor \(s=2\) every step.
If \(a_n\neq 0\) and \(\{z_k\}\) is given, the equation
\[y_{k+n}+a_1y_{k+n-1}+\cdots+a_{n-1}y_{k+1}+a_ny_k=z_k\quad\text{for all } k \tag{5}\]has exactly one solution for each choice of the \(n\) initial values \(y_0,\dots,y_{n-1}\).
The set \(H\) of all solutions of the \(n\text{th}\)-order homogeneous equation
\[y_{k+n}+a_1y_{k+n-1}+\cdots+a_{n-1}y_{k+1}+a_ny_k=0\quad\text{for all } k \tag{6}\]is an \(n\)-dimensional vector space.
Find a basis for the set of all solutions of equation (4), \(y_{k+3}-4y_{k+2}+y_{k+1}+6y_k=0\).
Solution
From Example 1, \(\{2^k\}\), \(\{(-1)^k\}\) and \(\{3^k\}\) are solutions, and by the Casorati test (\(\det C(0)=-12\)) they are linearly independent. The equation has order \(3\), so by Theorem 20 the solution space is \(3\)-dimensional. Three linearly independent vectors in a \(3\)-dimensional space form a basis (the Basis Theorem). So \(\{2^k\},\{(-1)^k\},\{3^k\}\) is a basis, and every solution is
\[y_k=c_1\,2^k+c_2(-1)^k+c_3\,3^k\]for some scalars \(c_1,c_2,c_3\). Such a basis is called a fundamental set of solutions, and the formula is the general solution. Verifying directly that the three signals span the solution space would be hard; the dimension count does it for us.
Find the solution of (4) with \(y_0=1\), \(y_1=6\), \(y_2=12\), and compute \(y_3\) in two ways.
Solution
Put \(k=0,1,2\) into the general solution \(y_k=c_1\,2^k+c_2(-1)^k+c_3\,3^k\):
\[\begin{aligned} c_1+c_2+c_3 &= 1\\ 2c_1-c_2+3c_3 &= 6\\ 4c_1+c_2+9c_3 &= 12\end{aligned}\]The coefficient matrix is the Casorati matrix \(C(0)\) of these three signals. Add the first two equations: \(3c_1+4c_3=7\). Add the second and third: \(6c_1+12c_3=18\), so \(c_1+2c_3=3\). Subtract \(3\) times this from \(3c_1+4c_3=7\): \(-2c_3=-2\), so \(c_3=1\), \(c_1=1\), and \(c_2=1-1-1=-1\). Hence
\[y_k=2^k-(-1)^k+3^k.\]Two ways to get \(y_3\): from the formula, \(8-(-1)+27=36\); from the equation, \(y_3=4y_2-y_1-6y_0=48-6-6=36\). They agree.
Enter the coefficients of \(y_{k+2}+a\,y_{k+1}+b\,y_k=0\) and two initial values. The figure shows the solution for \(k=0,\dots,15\), and the readout gives the roots of the auxiliary equation \(r^2+ar+b=0\) and the general solution. Try \(a=-1,b=-1\) (Fibonacci), \(a=0,b=4\) (Example 2), \(a=-1.4,b=0.98\) (decaying oscillation) and \(a=-0.5,b=-0.5\).
4.2 Nonhomogeneous equations
The general solution of the nonhomogeneous equation (5) is
\[\{y_k\}=\{p_k\}+c_1\{u^{(4)}_k\}+\cdots+c_n\{u^{(n)}_k\},\]one particular solution \(\{p_k\}\) of (5) plus an arbitrary combination of a fundamental set of solutions of the corresponding homogeneous equation (6). The reason is the same as for \(A\mathbf x=\mathbf b\) and \(A\mathbf x=\mathbf 0\): the transformation \(T\) is linear, so the difference of two solutions of \(T(\mathbf y)=\mathbf z\) is in the kernel of \(T\). The solution set is the subspace \(H\) of (6) translated by \(\{p_k\}\).
A loan of \(5000\) has an interest rate of \(2\%\) per month, and \(300\) is paid at the end of every month. Let \(y_k\) be the balance just after the \(k\text{th}\) payment, with \(y_0=5000\). Find a formula for \(y_k\) and decide when the loan is paid off.
Solution
Each month, interest of \(2\%\) is added and then \(300\) is paid: \(y_{k+1}=1.02\,y_k-300\), that is,
\[y_{k+1}-1.02\,y_k=-300,\]a first-order nonhomogeneous equation. First look for a constant particular solution \(y_k=T\): \(T-1.02T=-300\) gives \(T=15000\). (This is the balance that would stay the same forever: \(2\%\) of \(15000\) is exactly the \(300\) paid.) The homogeneous equation \(y_{k+1}-1.02y_k=0\) has the auxiliary equation \(r-1.02=0\), so its solutions are the multiples of \(\{1.02^k\}\). General solution: \(y_k=15000+c\,(1.02)^k\). The initial value gives \(5000=15000+c\), so \(c=-10000\) and
\[y_k=15000-10000\,(1.02)^k.\]Check: \(y_1=15000-10200=4800\), and directly \(1.02\cdot 5000-300=4800\). The balance reaches \(0\) when \((1.02)^k=1.5\), that is \(k=\ln 1.5/\ln 1.02\approx 20.5\). So \(y_{20}=15000-10000(1.02)^{20}\approx 140.53\) is still positive, and the \(21\)st payment, of about \(1.02\cdot 140.53\approx 143.34\), pays off the loan. The borrower makes \(20\) payments of \(300\) and a last payment of \(143.34\).
Self-check only. In (a) more than one answer is correct; the check tests whether your \(r\) works.
4.3 Reduction to a first-order system
A modern way to handle an \(n\text{th}\)-order equation is to replace it by a system of first-order equations, written as \(\mathbf x_{k+1}=A\mathbf x_k\) with vectors \(\mathbf x_k\) in \(\mathbb R^n\) and an \(n\times n\) matrix \(A\). Chapter 5 studies such systems through the eigenvalues of \(A\).
Write equation (4), \(y_{k+3}-4y_{k+2}+y_{k+1}+6y_k=0\), as a first-order system.
Solution
For each \(k\), collect three consecutive values into a vector: \(\mathbf x_k=\begin{bmatrix} y_k\\ y_{k+1}\\ y_{k+2}\end{bmatrix}\). The equation says \(y_{k+3}=-6y_k-y_{k+1}+4y_{k+2}\), so
\[\mathbf x_{k+1}=\begin{bmatrix} y_{k+1}\\ y_{k+2}\\ y_{k+3}\end{bmatrix}=\begin{bmatrix} 0\cdot y_k+1\cdot y_{k+1}+0\cdot y_{k+2}\\ 0\cdot y_k+0\cdot y_{k+1}+1\cdot y_{k+2}\\ -6y_k-y_{k+1}+4y_{k+2}\end{bmatrix}=\begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ -6 & -1 & 4\end{bmatrix}\begin{bmatrix} y_k\\ y_{k+1}\\ y_{k+2}\end{bmatrix}.\]That is, \(\mathbf x_{k+1}=A\mathbf x_k\) with \(A=\begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ -6 & -1 & 4\end{bmatrix}\). The first two rows just move the window one step; the last row is the difference equation. Given \(\mathbf x_0=(y_0,y_1,y_2)\), the whole solution is \(\mathbf x_k=A^k\mathbf x_0\).
The equation \(y_{k+n}+a_1y_{k+n-1}+\cdots+a_{n-1}y_{k+1}+a_ny_k=0\) for all \(k\) is equivalent to \(\mathbf x_{k+1}=A\mathbf x_k\) for all \(k\), where
\[\mathbf x_k=\begin{bmatrix} y_k\\ y_{k+1}\\ \vdots\\ y_{k+n-1}\end{bmatrix},\qquad A=\begin{bmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & & 0\\ \vdots & & & \ddots & \vdots\\ 0 & 0 & 0 & & 1\\ -a_n & -a_{n-1} & -a_{n-2} & \cdots & -a_1\end{bmatrix}.\]The last row holds the negatives of the coefficients, in reverse order. A preview of Chapter 5: for the matrix of Example 6, \(\det(rI-A)=r^3-4r^2+r+6\), the auxiliary polynomial of the equation. The roots of the auxiliary equation are the eigenvalues of \(A\).
Self-check only.
Write \(y_{k+3}+2y_{k+2}-y_{k+1}-2y_k=0\) as \(\mathbf x_{k+1}=A\mathbf x_k\) with \(\mathbf x_k=(y_k,y_{k+1},y_{k+2})\). Enter \(A\).
Solve for the newest term: \(y_{k+3}=2y_k+y_{k+1}-2y_{k+2}\). So
\[A=\begin{bmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 2 & 1 & -2\end{bmatrix}.\]Homework 10-11
- Fill in your name and surname below before you save the PDF.
- Show your work. For each step, name the theorem, the row operation or the reason you use. An answer without the steps that lead to it does not receive full credit.
- Every question has two answer modes: Type and Write by hand. In Write by hand mode the text boxes are replaced by a writing area where you can write with a pen, your finger or the mouse. For each question, only the answer of the selected mode goes into the PDF. Changing the mode does not delete what you entered in the other mode.
- In Type mode, write a vector as
(1, -2, 3), a matrix as[1 2; 3 4](rows separated by semicolons), and a signal by listing its entries with the \(k=0\) entry marked, for example(..., 0, [1], 2, 0, ...). - To submit: press "Save homework as PDF", choose "Save as PDF" in the print dialog, and upload the file to Canvas.
- Your answers are saved automatically in this browser. If you open the page on a different computer or browser, they will not be there.
Question 120 points
Question 220 points
Question 320 points
Question 425 points
Consider the difference equation
\[y_{k+2}-y_{k+1}-6y_k=0\quad\text{for all } k.\]Question 515 points
A loan of \(6000\) has an interest rate of \(1\%\) per month. At the end of every month, interest is added and a payment of \(200\) is made. Let \(y_k\) be the balance just after the \(k\text{th}\) payment, with \(y_0=6000\).