We can write a periodic signal $x$ as a linear combination of terms:
\begin{align*}
x &= X_0\Psi_0 + X_1\Psi_1 + \cdots + X_{p-1}\Psi_{p-1} 
\end{align*}

Since we are familiar with the linear algebraic language, we can write this in a much more compact form. First we can write $X$ as a $p \times 1$ matrix:
\begin{align*}
X = \left[ \begin{array}{c} X_0 \\ X_1 \\ \vdots \\ X_{p-1} \\ \end{array} \right] 
\end{align*}


We know that $\Psi_k(n) = e^{ik\omega_0 n}$, where $\omega_0 = 2\pi/p$. We can then write $\Psi_k$ as:

\begin{align*}
\Psi_k = \left[ \begin{array}{c} \Psi_k(0) \\ \Psi_k(1) \\ \vdots \\ \Psi_k(p-1) \\ \end{array} \right] = \left[ \begin{array}{c} 1 \\ e^{ik\omega_0} \\ \vdots \\ e^{ik\omega_0(p-1)} \\ \end{array} \right] \\
\end{align*}


Remember that the $k^{th}$ function, or basis signal is denoted by $e^{ik\omega}$, not $e^{i\omega n}$. We don't use $p$ as a value because $e^{ik\omega_0 p}=e^{ik2\pi}$, so we don't need any more terms. We have already shown that these basis signals are orthogonal, hence we can write:

\begin{align*}
\Psi_k^T\Psi_\ell^* &= p\delta(k-\ell) = \left[ \begin{array}{rr} 0 & k\neq\ell \\ p & k=l \\ \end{array} \right] \\
\lr{\Psi_k^T}^*\Psi_\ell &= p\delta(k-\ell) = \left[ \begin{array}{rr} 0 & k\neq\ell \\ p & k=l \\ \end{array} \right] \quad \mbox{take the conjugate of both sides}\\
\Psi_k^H\Psi_\ell &= p\delta(k-\ell) = \left[ \begin{array}{rr} 0 & k\neq\ell \\ p & k=l \\ \end{array} \right] \\
\end{align*}


Here we can define the \emph{Hermitian Transpose} as the conjugate of the transpose:

\begin{nicebox}
$$ \lr{\Psi_k^T}^* = \Psi_k^H $$
\end{nicebox}

Now we can continue with our signal $x$. So now let's go back to initial equation, $x = X_0\Psi_0 + X_1\Psi_1 + \cdots + X_{p-1}\Psi_{p-1}$. Lets write this in a slightly different form by creating a matrix with columns that are made up of the basis vectors multiplied by a coefficient matrix:

\begin{align*}
x &= 
\left[
\begin{array}{cccc}
\Psi_0(0) & \Psi_1(0) & \cdots & \Psi_{p-1}(0) \\
\Psi_0(1) & \Psi_1(1) & \cdots & \Psi_{p-1}(1) \\
\vdots & \vdots & \ddots & \vdots \\
\Psi_0(p-1) & \Psi_1(p-1) & \cdots & \Psi_{p-1}(p-1) \\
\end{array}
\right]
\left[ \begin{array}{c} X_0 \\ X_1 \\ \vdots \\ X_{p-1} \\ \end{array} \right]
\\
x &= \left[ \begin{array}{rrrr} \Psi_0 & \Psi_1 & \cdots & \Psi_{p-1} \\ \end{array} \right] \left[ \begin{array}{c} X_0 \\ X_1 \\ \vdots \\ X_{p-1} \\ \end{array} \right] \\
x &= \Psi X
\end{align*}

This is the synthesis equation. This is exactly what tells us how to obtain $x$ by the linear combination of coefficients in $X$ and exponential vectors in the matrix $\Psi$. How do we solve for $X$? What we are after is the coefficients. These coefficients are what  determine the linear combination of the complex exponential basis vectors that would in turn produce the signal in the period $p$. To do this, we use some more linear algebra:

\begin{align*}
x &= \Psi X \\
\Psi^{-1}x &= \Psi^{-1}\Psi X \\
\Psi^{-1}x &= X \\
X &= \Psi^{-1}x
\end{align*}

But in our case, we don't need to invert $\Psi$ explicity. Taking inverses is numerically expensive, so any opportunity to work around it should be taken. We can multiply by the Hermitian Transpose of $\Psi$:
$$
\Psi^H =  \left[ \begin{array}{c} \Psi_0^H \\ \Psi_1^H \\ \vdots \\ \Psi_{p-1}^H \\ \end{array} \right] 
$$
where each $\Psi_k^H$ is a $1 \times p$ row:

$$
\Psi_k^H = \left[ \begin{array}{rrrr} \Psi_k(0)^H & \Psi_k(1)^H & \cdots & \Psi_k(p-1)^H \\ \end{array} \right]
$$

Hence we have the matrix:

$$
\Psi^H = 
\left[
\begin{array}{cccc}
\Psi_0^H(0) & \Psi_0^H(1) & \cdots & \Psi_0^H(p-1) \\
\Psi_1^H(0) & \Psi_1^H(1) & \cdots & \Psi_1^H(p-1) \\
\vdots & \vdots & \ddots & \vdots \\
\Psi_{p-1}^H(0) & \Psi_{p-1}^H(1) & \cdots & \Psi_{p-1}^H(p-1) \\
\end{array}
\right]
$$

So when we multiply $\Psi^H\Psi$, we get:

$$
\Psi^H\Psi =
\left[
\begin{array}{cccc}
\Psi_0^H(0) & \Psi_0^H(1) & \cdots & \Psi_0^H(p-1) \\
\Psi_1^H(0) & \Psi_1^H(1) & \cdots & \Psi_1^H(p-1) \\
\vdots & \vdots & \ddots & \vdots \\
\Psi_{p-1}^H(0) & \Psi_{p-1}^H(1) & \cdots & \Psi_{p-1}^H(p-1) \\
\end{array}
\right]
\left[
\begin{array}{cccc}
\Psi_0(0) & \Psi_1(0) & \cdots & \Psi_{p-1}(0) \\
\Psi_0(1) & \Psi_1(1) & \cdots & \Psi_{p-1}(1) \\
\vdots & \vdots & \ddots & \vdots \\
\Psi_0(p-1) & \Psi_1(p-1) & \cdots & \Psi_{p-1}(p-1) \\
\end{array}
\right]
$$

Lets just simplify things a bit and keep a compact form by using row vectors and column vectors in our matrices:

\begin{align*}
\Psi^H\Psi &=   \left[ \begin{array}{c} \Psi_0^H \\ \Psi_1^H \\ \vdots \\ \Psi_{p-1}^H \\ \end{array} \right] \left[ \begin{array}{rrrr} \Psi_0 & \Psi_1 & \cdots & \Psi_{p-1} \\ \end{array} \right] \\
\Psi^H\Psi &= \left[
\begin{array}{cccc}
\Psi_0^H\Psi_0 & \Psi_0^H\Psi_1 & \cdots & \Psi_0^H\Psi_{p-1} \\
\Psi_1^H\Psi_0 & \Psi_1^H\Psi_1 & \cdots & \Psi_1^H\Psi_{p-1} \\
\vdots & \vdots & \ddots & \vdots \\
\Psi_{p-1}^H\Psi_0 & \Psi_{p-1}^H\Psi_1 & \cdots & \Psi_{p-1}^H\Psi_{p-1} \\
\end{array}
\right] \\
\Psi^H\Psi &= \left[
\begin{array}{cccc}
p & 0 & \cdots & 0 \\
0 & p & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & p \\
\end{array}
\right] \\
\Psi^H\Psi &= pI \\
\end{align*}


We know that we get $p$ down the diagonal because of orthogonality as shown earlier:


$$
\Psi_k^H\Psi_\ell = p\delta(k-\ell) = \left[ \begin{array}{rr} 0 & k\neq\ell \\ p & k=l \\ \end{array} \right] 
$$

Now lets find our analysis equation:

\begin{align*}
x &= \Psi X \\
\Psi^H x &= \Psi^H\Psi X \\
\Psi^H x &= pIX \\
\Psi^H x &= pX \\
\frac{1}{p}\Psi^H x &= X \\
X &= \frac{1}{p}\Psi^H x  \\
\end{align*}


Now we have our analysis equation in linear algebra form. To conclude, as long as the basis vectors are mutually orthogonal, and we assume that any inner product of a basis vector with itself is $p$, then this equation holds.

\begin{nicebox}
\begin{align*}
X &= \frac{1}{p}\Psi^H x \quad \quad & \mbox{(analysis equation)} \\
x &= \Psi X \quad \quad & \mbox{(synthesis equation)}
\end{align*}
\end{nicebox}

Discrete Fourier Series

\begin{example}

Find the DFS coefficients of the infinite duration impulse train:

% \img{images/deltas/periodic/dfs/dfs.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3.5,-3)(3.5,3)
   

\rput(-3.6,0.4){$\cdots$} 
\rput(4,0.4){$\cdots$} 

% line
\psline{-*}(-3,0)(-3,1)
%  value
\rput(-2.7,1){(1)}
%  position
\rput(-3,-0.3){-p}


% line
\psline{-*}(0,0)(0,1)
%  value
\rput(0.3,1){(1)}
%  position
\rput(0,-0.3){0}


% line
\psline{-*}(3,0)(3,1)
%  value
\rput(3.3,1){(1)}
%  position
\rput(3,-0.3){p}

% axes
\psline{->}(-4,0)(4,0)
\rput(4,-0.3){ $n$ }
\rput(4,1){ $x(n)$ }

\end{pspicture}
\end{center}

$$ x(n) = \sum \limits_{\ell=-\infty}^\infty \delta(n-\ell p)$$

Lets use the analysis equation:

\begin{align*}
X_k &= \frac{1}{p} \sum \limits_{n=0}^{p-1}x(n)e^{-ik\omega_0 n} \\
X_k &= \frac{1}{p} \sum \limits_{n=0}^{p-1}\sum \limits_{\ell=-\infty}^\infty \delta(n-\ell p)e^{-ik\omega_0 n} \\
X_k &= \frac{1}{p} \sum \limits_{n=0}^{p-1}\delta(n)e^{-ik\omega_0 n} \\
X_k &= \frac{1}{p} e^{0} \\
X_k &= \frac{1}{p} 
\end{align*}

This implies that there is an equal contribution of all frequencies. The frequencies are $0, \omega_0, 2\omega_0, \dots, (p-1)\omega_0$. This signal corresponds to white noise. 
\end{example}


\begin{example}
Determine the signal $x: \Z \to \R$ given the following information:

\begin{enumerate}
\item $x(n+4\ell) = x(n) $ $\forall \ell \in \Z$
\item $\sum \limits_{n=-1}^2 x(n) = 2 $
\item $\sum \limits_{n=-1}^2 (-1)^nx(n) = 4 $
\item $\sum \limits_{n=-1}^2 x(n)\cos\lr{\frac{\pi}{2}n} = \sum \limits_{n=-1}^2 x(n)\sin\lr{\frac{\pi}{2}n} = 0$ 
\end{enumerate}

Since $x(n+4\ell) = x(n)$, this implies that we can use $p=4$ as a period. This does not necessarily mean that it is the fundamental period. Lets start by solving for $X_0$ using the analysis equation:

\begin{align*}
X_0 &= \frac{1}{4}\sum \limits_{n=-1}^2 x(n)e^{0} \\
X_0 &= \frac{1}{4}2 = \frac{1}{2} \\ 
\end{align*}

Now lets solve for $X_2$:

\begin{align*}
X_2 &= \frac{1}{4}\sum \limits_{n=-1}^2 x(n)e^{-i\pi n}  \\ 
X_2 &= \frac{1}{4}\sum \limits_{n=-1}^2 x(n)(-1)^n  \\ 
X_2 &= \frac{1}{4} 4 = 1  \\ 
\end{align*}

Note that if we choose either $X_{-1}$ or $X_1$, we get the same answer for the same reason:

\begin{align*}
X_{-1} &= \frac{1}{4}\sum \limits_{n=-1}^2 x(n)e^{-i\frac{\pi}{2} n}  \\ 
X_{-1} &= \frac{1}{4}\sum \limits_{n=-1}^2 x(n)\lr{\cos\lr{\frac{\pi}{2}n} + i\sin\lr{\frac{\pi}{2}n}}  \\ 
X_{-1} &= \frac{1}{4}\sum \limits_{n=-1}^2 x(n)\cos\lr{\frac{\pi}{2}n} + \frac{i}{4}\sum \limits_{n=-1}^2 x(n)\sin\lr{\frac{\pi}{2}n} \\ 
X_{-1} &= 0
\end{align*}

So we have
\begin{align*}
X_{-1} &= 0 \\
X_{0} &= \frac{1}{2} \\
X_{1} &= 0 \\
X_{2} &= 1 \\
\end{align*}

Now synthesize $x$:

\begin{align*}
x(n) &= X_0 + X_2e^{i\pi n} \\
x(n) &= \frac{1}{2} + (-1)^n 
\end{align*}

This actually has a fundamental period of two and a very high frequency. Note that it is safe to assume an integer multiple of the fundamental period. Our fundamental frequency is $2\pi/p = \pi$.

% \img{images/deltas/periodic/dfsex/final.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-1.5,-1)(3.5,3)
    

% line
\psline{-*}(-2,0)(-2,-0.5)
%  value
\rput(-1.5,-0.5){(-1/2)}
%  position
\rput(-2,0.3){-2}


% line
\psline{-*}(-1,0)(-1,1.5)
%  value
\rput(-0.5,1.5){(3/2)}
%  position
\rput(-1,-0.3){-1}


% line
\psline{-*}(0,0)(0,-0.5)
%  value
\rput(0.5,-0.5){(-1/2)}
%  position
\rput(0,0.3){0}


% line
\psline{-*}(1,0)(1,1.5)
%  value
\rput(1.5,1.5){(3/2)}
%  position
\rput(1,-0.3){1}


% line
\psline{-*}(2,0)(2,-0.5)
%  value
\rput(2.5,-0.5){(-1/2)}
%  position
\rput(2,0.3){2}


% line
\psline{-*}(3,0)(3,1.5)
%  value
\rput(3.5,1.5){(3/2)}
%  position
\rput(3,-0.3){3}

% axes
\psline{->}(-3,0)(4,0)
\rput(4,-0.3){ $n$ }
\rput(4.2,1.5){ $x(n)$ }

\rput(-3,0.75){$\cdots$}
\rput(4,0.75){$\cdots$}
\end{pspicture}
\end{center}

\end{example}

3 Week 3