Every Fourier representation pairs one domain with another, and discreteness in one domain forces periodicity in the other. The DTFT of Chapter 7 maps a discrete-time sequence to a continuous, periodic function $X(e^{j\omega})$ — useful analytically, but a computer cannot store a continuum of frequencies. The Discrete Fourier Transform（離散傅立葉變換）closes the loop: both domains are discrete and finite, so it is the only member of the family a computer can evaluate exactly.
| Transform | Time domain | Frequency domain |
|---|---|---|
| Fourier Series (FS) | continuous, periodic | discrete, aperiodic |
| Fourier Transform (FT) | continuous, aperiodic | continuous, aperiodic |
| DTFT | discrete, aperiodic | continuous, periodic ($2\pi$) |
| DFT | discrete, finite ($N$ points) | discrete, finite ($N$ points) |
Let $\tilde{x}[n]$ be periodic（週期性序列）with period $N$: $\tilde{x}[n] = \tilde{x}[n+N]$ for all $n$. Such a sequence is fully described by one period, and it can be expanded on the $N$ harmonically related complex exponentials $e^{j2\pi kn/N}$, $k = 0,\dots,N-1$. This is the Discrete Fourier Series（離散傅立葉級數, DFS）:
Both $\tilde{x}[n]$ and $\tilde{X}[k]$ are periodic with period $N$. The DFT defined next is numerically identical to one period of the DFS — the only difference is interpretation: the DFT treats $x[n]$ as a finite-length sequence on $0 \le n \le N-1$, while the DFS treats it as one period of an infinitely repeating signal.
Take a finite-length sequence $x[n]$, $0 \le n \le L-1$, with DTFT $X(e^{j\omega})$. Evaluate (sample) the DTFT at $N$ equally spaced frequencies $\omega_k = 2\pi k/N$:
Sampling in frequency causes periodization in time — the exact dual of Chapter 4, where sampling in time periodized the spectrum. Inverting the $N$ frequency samples returns not $x[n]$ itself but its periodic superposition:
Define the twiddle factor（旋轉因子）$W_N$, the principal $N$-th root of unity:
Useful identities, used constantly in derivations and in the FFT of the next chapter:
Notation: we write $x[n] \;\overset{\text{DFT}}{\longleftrightarrow}\; X[k]$, and $((n))_N$ means $n$ modulo $N$（$n$ 對 $N$ 取餘數）.
Proof that IDFT inverts the DFT. Substitute the DFT into the IDFT and swap sums:
$$\frac{1}{N}\sum_{k=0}^{N-1}\left(\sum_{m=0}^{N-1} x[m] W_N^{km}\right) W_N^{-kn} = \sum_{m=0}^{N-1} x[m] \underbrace{\frac{1}{N}\sum_{k=0}^{N-1} W_N^{k(m-n)}}_{=\;\delta[((m-n))_N]} = x[n].$$The inner sum is the orthogonality identity above — it acts as a Kronecker delta and sifts out exactly the term $m=n$.
The most important transform pair of the chapter: the length-$L$ rectangular pulse $x[n] = 1$, $0\le n\le L-1$. Its DTFT is a geometric series:
The magnitude $\left|\sin(\omega L/2)/\sin(\omega/2)\right|$ is the periodic sinc: main-lobe peak $L$ at $\omega = 0$, zeros at $\omega = 2\pi m/L$ ($m$ not a multiple of $L$), main-lobe width $4\pi/L$, and — unlike the continuous sinc — it is $2\pi$-periodic and returns to height $L$ at every multiple of $2\pi$.
Now sample it. With $N = L = 8$, every DFT sample except $k=0$ lands exactly on a zero crossing of the periodic sinc — the DFT sees only $X[0]=8$ and looks deceptively like an impulse. With $N = 32$ (zero padding the same 8 samples), the DFT samples trace out the full lobe structure:
Because the DFT is a linear map from $N$ samples to $N$ coefficients, it is a matrix–vector product. Stack the signal into $\mathbf{x} = \begin{bmatrix} x[0] & x[1] & \cdots & x[N-1]\end{bmatrix}^{T}$ and define the $N \times N$ DFT matrix $\mathbf{W}_N$ with entries $[\mathbf{W}_N]_{k,n} = W_N^{kn}$:
$\mathbf{W}_N$ is a symmetric Vandermonde matrix（symmetric：$\mathbf{W}_N^{T} = \mathbf{W}_N$，因為 $W_N^{kn}=W_N^{nk}$）. For example,
$$\mathbf{W}_4 = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -j & -1 & j\\ 1 & -1 & 1 & -1\\ 1 & j & -1 & -j \end{bmatrix} \qquad (W_4 = e^{-j\pi/2} = -j).$$From the orthogonality identity, the rows of $\mathbf{W}_N$ are orthogonal with norm-squared $N$, so the inverse needs no Gaussian elimination:
Equivalently $\frac{1}{\sqrt{N}}\mathbf{W}_N$ is a unitary matrix（么正矩陣）. Two consequences:
MATLAB computes the DFT with fft and the IDFT with ifft (both use FFT algorithms regardless of whether $N$ is a power of two). Key conventions to remember:
X = fft(x) uses $N = $ length(x); X = fft(x, N) zero-pads or truncates to $N$ first.X(k+1). DC is X(1).fftshift recenters the spectrum.dftmtx(N), or build it directly as W.^(n'*k) as in Exercise 6.X(1) must equal sum(x). (2) For real $x$, X(N-k+1) = conj(X(k+1)) — magnitude plots must be symmetric about $N/2$. (3) sum(abs(x).^2) must equal sum(abs(X).^2)/N (Parseval). If any of these fail, the bug is in your indexing.
Linearity（線性）. If both sequences are defined on the same $N$-point grid, $a\,x_1[n] + b\,x_2[n] \;\longleftrightarrow\; a\,X_1[k] + b\,X_2[k]$. If lengths differ, zero-pad both to a common $N$ first.
Circular time shift（循環時間位移）. Because the DFT views $x[n]$ as one period of a periodic sequence, "shifting" means rotating the samples around a circle of circumference $N$:
Magnitude is untouched; only a linear phase ramp is added — exactly like the DTFT shift theorem, but with the shift interpreted modulo $N$. Samples pushed past $n = N-1$ wrap around to $n = 0$:
Circular frequency shift / modulation（調變）. The dual statement:
Circular time reversal（循環時間反轉）. Reversal modulo $N$ keeps $x[0]$ in place and reverses the rest: $x[((-n))_N] = x[((N-n))_N]$, i.e. $\{x[0], x[N-1], x[N-2], \dots, x[1]\}$.
Conjugate symmetry for real signals（實數訊號的共軛對稱）. Combining the two: if $x[n]$ is real, then
So a real $N$-point signal has only about $N/2$ independent spectral values: bins $k$ and $N-k$ are mirror images. $X[0]$ is always real, and for even $N$ so is $X[N/2]$.
Duality（對偶性）. The DFT and IDFT have nearly the same form, so transforming twice almost returns the signal:
Example: $\delta[n] \leftrightarrow 1$ (all $k$), and dually the all-ones sequence $\leftrightarrow N\delta[k]$ — exactly Examples 8-1(a) and (b).
Parseval's relation（能量守恆）. Direct consequence of $\frac{1}{\sqrt N}\mathbf{W}_N$ being unitary:
| Property | Time domain | Frequency domain |
|---|---|---|
| Linearity | $a x_1[n] + b x_2[n]$ | $a X_1[k] + b X_2[k]$ |
| Circular time shift | $x[((n-m))_N]$ | $W_N^{km} X[k]$ |
| Circular frequency shift | $W_N^{-ln} x[n]$ | $X[((k-l))_N]$ |
| Circular time reversal | $x[((-n))_N]$ | $X[((-k))_N]$ |
| Conjugation | $x^{*}[n]$ | $X^{*}[((-k))_N]$ |
| Duality | $X[n]$ | $N\,x[((-k))_N]$ |
| Circular convolution | $x_1[n] \circledast x_2[n]$ | $X_1[k]\, X_2[k]$ |
| Multiplication | $x_1[n]\, x_2[n]$ | $\tfrac{1}{N}\, X_1[k] \circledast X_2[k]$ |
| Conjugate symmetry (real $x$) | $x[n]$ real | $X[k] = X^{*}[N-k]$ |
| Parseval | $\sum_n |x[n]|^2$ | $= \tfrac{1}{N}\sum_k |X[k]|^2$ |
What time-domain operation corresponds to multiplying two DFTs? Not linear convolution — because of the implicit periodicity, it is circular convolution（循環摺積）, written $\circledast$ or $\overset{N}{\circledast}$:
Mechanically it is the same flip-shift-multiply-sum recipe as linear convolution, except the flip and shift are circular: $x_2$ is reversed around the circle and rotated by $n$ positions. Both sequences must be defined on (or zero-padded to) the same length $N$, and the output also has length $N$.
Let $x_1[n] = \{1, 1, 1, 1\}$ and $x_2[n] = \{1, 2, 3, 4\}$, $N = 4$.
Let $x_1$ have length $L$ and $x_2$ length $P$. Their linear convolution $y_{\text{lin}}[n] = x_1[n] * x_2[n]$ has length $L + P - 1$. The $N$-point circular convolution is the linear result wrapped around a circle of length $N$:
If $N \ge L+P-1$ nothing wraps and $y_c = y_{\text{lin}}$. If $N$ is too small, the tail of $y_{\text{lin}}$ folds back onto its head — time aliasing again, this time caused by multiplying spectra sampled too coarsely.
The fast-convolution recipe（快速摺積流程）:
Cost: three FFTs plus $N$ multiplies $\approx \tfrac{3}{2}N\log_2 N + N$ complex multiplications, versus $LP$ for direct convolution — a huge win when both sequences are long. In MATLAB: y = ifft( fft(x1,N) .* fft(x2,N) ).
Filtering a very long (possibly streaming) signal $x[n]$ with a length-$P$ FIR impulse response $h[n]$ cannot wait for the whole signal. Overlap-add（重疊相加法）processes it block by block:
Linearity of convolution guarantees the sum is exactly $x[n]*h[n]$: since $x[n] = \sum_r x_r[n-rL]$, convolving term by term gives $y[n] = \sum_r (x_r * h)[n-rL]$.
Appending zeros to a length-$L$ signal before taking an $N$-point DFT ($N > L$) does not change its DTFT at all — the extra terms contribute nothing to the sum. It only changes where the DTFT is sampled: the grid spacing shrinks from $2\pi/L$ to $2\pi/N$. Zero padding（補零）therefore:
Resolution is governed by the window's main-lobe width: a length-$L$ rectangular window has main-lobe width $4\pi/L$ (rad/sample), so two real tones closer than about $F_s/L$ Hz produce overlapping main lobes that merge into one bump. More data — not more zeros — is the only cure:
What if the signal is not time-limited? Keeping only $N$ samples is equivalent to multiplying by a window（窗函數）: $x_w[n] = x[n]\,w[n]$. By the multiplication property, the spectrum becomes a convolution:
Each spectral line of $x[n]$ is replaced by a copy of the window's frequency response $W(e^{j\omega})$ — main lobe (width = blur) plus sidelobes (leakage). The windows highlighted in the lecture:
| Window ($0 \le n \le N-1$) | $w[n]$ | Main-lobe width | Peak sidelobe |
|---|---|---|---|
| Rectangular（矩形窗） | $1$ | $4\pi/N$ | $-13$ dB |
| Triangular / Bartlett（三角窗） | $1 - \dfrac{\left|\,n - \frac{N-1}{2}\right|}{\frac{N-1}{2}}$ | $8\pi/N$ | $-27$ dB |
| Generalized Hanning（廣義漢寧窗） | $\alpha - (1-\alpha)\cos\dfrac{2\pi n}{N-1}$ | $8\pi/N$ | — |
| · Hann ($\alpha = 0.5$) | $0.5 - 0.5\cos\dfrac{2\pi n}{N-1}$ | $8\pi/N$ | $-31$ dB |
| · Hamming ($\alpha = 0.54$) | $0.54 - 0.46\cos\dfrac{2\pi n}{N-1}$ | $8\pi/N$ | $-41$ dB |
The spectrum of a windowed sinewave is the window response shifted to the tone frequency. For closely spaced sinewaves there is leakage（洩漏）between their spectra: the sidelobes of a strong tone can completely bury a nearby weak tone. The lecture's example — three sinewaves analyzed with rectangular vs. Hamming windows — reproduced numerically:
Computational cost? Applying a window costs only $N$ extra multiplications before the FFT — negligible compared to the $\frac{N}{2}\log_2 N$ butterflies of the transform itself. Window choice is essentially free performance.
$X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}$, $\;x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k] W_N^{-kn}$, with $W_N = e^{-j2\pi/N}$. The DFT equals the DTFT sampled at $\omega_k = 2\pi k/N$ (exact iff signal length $\le N$), and equals one period of the DFS.
$\mathbf{X} = \mathbf{W}_N \mathbf{x}$ with $[\mathbf{W}_N]_{kn} = W_N^{kn}$; symmetric, and $\mathbf{W}_N^{-1} = \mathbf{W}_N^{*}/N$, so $\mathbf{W}_N/\sqrt{N}$ is unitary. Direct cost $\mathcal{O}(N^2)$; the FFT brings it to $\mathcal{O}(N\log_2 N)$.
Shift → phase ramp $W_N^{km}X[k]$; reversal/conjugation flip $k$; real signals give $X[k]=X^*[N-k]$; duality $X[n] \leftrightarrow N x[((-k))_N]$; Parseval $\sum|x|^2 = \frac{1}{N}\sum|X|^2$.
$X_1[k]X_2[k] \leftrightarrow$ circular convolution = linear convolution aliased mod $N$. For linear convolution zero-pad to $N \ge L+P-1$. Long signals: overlap-add with length-$L$ blocks, $N$-point FFTs, add the $P-1$ overlapping tail samples.
Refines the frequency grid to $F_s/N$ (interpolates the same DTFT) but resolution stays $\approx F_s/L$, set by the actual data length $L$. More data, not more zeros, separates close tones.
Truncation multiplies by $w[n]$ → spectrum convolved with $W(e^{j\omega})$. Rectangular: narrowest main lobe ($4\pi/N$), $-13$ dB sidelobes. Hann/Hamming: $8\pi/N$ main lobe, $-31$/$-41$ dB sidelobes. Trade resolution for leakage suppression.
Problem: Compute the 4-point DFT of $x[n] = \{1, 2, 3, 4\}$ using the DFT matrix $\mathbf{W}_4$. Verify your answer with Parseval's relation, and state which symmetry property your result must satisfy and check it.
With $W_4 = e^{-j\pi/2} = -j$:
$$\mathbf{X} = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -j & -1 & j\\ 1 & -1 & 1 & -1\\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix}1\\2\\3\\4\end{bmatrix} = \begin{bmatrix} 10\\ (1-3) + (-2+4)j\\ 1-2+3-4\\ (1-3) + (2-4)j \end{bmatrix} = \begin{bmatrix}10\\ -2+2j\\ -2\\ -2-2j\end{bmatrix}$$Parseval check: $\sum_n |x[n]|^2 = 1+4+9+16 = 30$, and $\frac{1}{4}\sum_k |X[k]|^2 = \frac{1}{4}(100 + 8 + 4 + 8) = \frac{120}{4} = 30$. ✓
Symmetry check: $x[n]$ is real, so we need $X[k] = X^{*}[4-k]$: indeed $X[1] = -2+2j = (X[3])^{*} = (-2-2j)^{*}$ ✓, and $X[0]=10$, $X[2]=-2$ are both real as required. Also $X[0] = \sum_n x[n] = 10$ ✓.
Problem: Let $X[k]$ be the $N$-point DFT of a real sequence $x[n]$. Express in terms of $X[k]$: (a) the DFT of $y_1[n] = x[((n-2))_N]$; (b) the DFT of $y_2[n] = x[((-n))_N]$; (c) the DFT of $y_3[n] = (-1)^n x[n]$ for even $N$; (d) the value of $\sum_{k=0}^{N-1} X[k]$.
(a) Circular shift property with $m=2$: $Y_1[k] = W_N^{2k} X[k] = e^{-j4\pi k/N}\,X[k]$. Same magnitude, linear phase added.
(b) Circular reversal: $Y_2[k] = X[((-k))_N] = X[N-k]$. Since $x[n]$ is real, $X[N-k] = X^{*}[k]$, so $Y_2[k] = X^{*}[k]$.
(c) $(-1)^n = e^{j\pi n} = e^{j\frac{2\pi}{N}\cdot\frac{N}{2}n} = W_N^{-\frac{N}{2}n}$, so by the circular frequency-shift property $Y_3[k] = X[((k - N/2))_N]$ — the spectrum rotated by half: low and high frequency bins swap.
(d) From the IDFT at $n=0$: $x[0] = \frac{1}{N}\sum_k X[k]$, hence $\sum_{k=0}^{N-1} X[k] = N\,x[0]$. (Dual of $X[0] = \sum_n x[n]$.)
Problem: Let $x_1[n] = \{1, 1, 1, 1\}$ and $x_2[n] = \{1, 2, 3, 4\}$. (a) Compute the linear convolution $y_{\text{lin}}[n] = x_1[n] * x_2[n]$. (b) Compute the 4-point circular convolution and explain its values using the time-aliasing relation $y_c[n] = \sum_r y_{\text{lin}}[n+rN]$. (c) What is the minimum DFT length $N$ for which the circular convolution equals the linear one? Verify for that $N$.
(a) $x_1$ is a length-4 moving-sum window over $x_2$: $$y_{\text{lin}}[n] = \{1,\; 1{+}2,\; 1{+}2{+}3,\; 1{+}2{+}3{+}4,\; 2{+}3{+}4,\; 3{+}4,\; 4\} = \{1, 3, 6, 10, 9, 7, 4\}$$ of length $L+P-1 = 7$.
(b) With $N=4$, fold the linear result modulo 4 ($y_c[n] = y_{\text{lin}}[n] + y_{\text{lin}}[n+4]$):
| $n$ | $y_{\text{lin}}[n]$ | $y_{\text{lin}}[n+4]$ | $y_c[n]$ |
|---|---|---|---|
| 0 | 1 | 9 | 10 |
| 1 | 3 | 7 | 10 |
| 2 | 6 | 4 | 10 |
| 3 | 10 | — | 10 |
So $y_c[n] = \{10,10,10,10\}$ — matching Example 8-3 and the middle panel of Fig. 8-3. The tail $\{9,7,4\}$ wrapped onto the head $\{1,3,6\}$.
(c) Need $N \ge L+P-1 = 7$. With $N=7$, zero-pad both to length 7; no term wraps ($y_{\text{lin}}[n+7] = 0$ for $0 \le n \le 6$), so the 7-point circular convolution is exactly $\{1,3,6,10,9,7,4\}$ — the right panel of Fig. 8-3.
Problem: Let $x[n] = a^n u[n]$ with $|a| < 1$ — an infinite-length sequence with DTFT $X(e^{j\omega}) = \dfrac{1}{1 - a e^{-j\omega}}$. Sample the DTFT at $\omega_k = 2\pi k/N$ to obtain $N$ numbers $X[k] = X(e^{j2\pi k/N})$, then take the $N$-point IDFT. Find a closed form for the resulting sequence $\hat{x}[n]$, $0 \le n \le N-1$, and compare it with $x[n]$.
Frequency sampling periodizes time: the IDFT of the samples is $$\hat{x}[n] = \sum_{r=-\infty}^{\infty} x[n - rN] = \sum_{r \le 0} a^{\,n-rN}\,u[n-rN].$$ For $0 \le n \le N-1$ the step is satisfied for all $r \le 0$ (i.e. shifts by $0, N, 2N, \dots$ to the left bring copies of the tail into the window), so with $m = -r \ge 0$: $$\hat{x}[n] = \sum_{m=0}^{\infty} a^{\,n+mN} = a^n \sum_{m=0}^{\infty} (a^N)^m = \boxed{\;\frac{a^n}{1 - a^N}, \qquad 0 \le n \le N-1.\;}$$
Comparison: $\hat{x}[n] = x[n]/(1-a^N) > x[n]$ — every sample is inflated by the folded-in tail of the infinite sequence. This is pure time aliasing: $x[n]$ has length $> N$ (infinite), so $N$ frequency samples cannot represent it. The error factor $\frac{1}{1-a^N} \to 1$ as $N \to \infty$ (or as $|a|^N \to 0$), so taking enough frequency samples makes the aliasing negligible. E.g. $a = 0.9$, $N = 10$: $a^N \approx 0.349$, a 54% inflation at every sample; $N = 100$: $a^N \approx 2.7\times 10^{-5}$, negligible.
Problem: A signal sampled at $F_s = 8$ kHz contains two sinusoids at $1000$ Hz and $1025$ Hz. (a) Using a rectangular window, estimate the minimum number of data samples $L$ needed to resolve the two tones. (b) If you capture only $L = 256$ samples but compute a $4096$-point DFT (zero padding), will the tones be resolved? Explain. (c) Repeat (a) for a Hamming window (main-lobe width $8\pi/L$). (d) What bin spacing (in Hz) does the 4096-point DFT give, and what is it good for here?
(a) Two tones separated by $\Delta f = 25$ Hz need the main lobes to be distinguishable, requiring approximately $$\Delta f \ge \frac{F_s}{L} \;\Longrightarrow\; L \ge \frac{F_s}{\Delta f} = \frac{8000}{25} = 320 \text{ samples}.$$
(b) No. With $L = 256 < 320$, the underlying windowed DTFT already has the two main lobes merged ($F_s/L = 31.25$ Hz $> 25$ Hz). Zero padding to 4096 samples that same merged DTFT on a finer grid — it draws the single bump more smoothly but cannot split it. Resolution depends on $L$, not $N$.
(c) The Hamming main lobe is twice as wide ($8\pi/L$ instead of $4\pi/L$), so roughly $$L \ge \frac{2F_s}{\Delta f} = \frac{2 \times 8000}{25} = 640 \text{ samples}.$$ The reward for the doubled length requirement is $-41$ dB sidelobes instead of $-13$ dB — essential if the two tones have very different amplitudes (cf. Fig. 8-6).
(d) Bin spacing $= F_s/N = 8000/4096 \approx 1.95$ Hz. Once the tones are resolved (with $L$ large enough), this fine grid lets you locate each peak to within $\pm 1$ Hz without interpolation — that is the legitimate use of zero padding.
Problem: A 5 Hz cosine is sampled at $F_s = 100$ Hz for exactly 1 second ($N = 100$ samples): $x[n] = \cos(2\pi \cdot 5 \cdot nT)$, $T = 1/F_s$.
(a) Build the $N \times N$ DFT matrix from the twiddle factor and use it to compute $X[k]$.
(b) Build the IDFT matrix from it and reconstruct $x[n]$.
(c)–(d) Repeat with MATLAB's fft / ifft and confirm the results agree.
(e) Plot $|X[k]|$ and the reconstructed $x[n]$ with stem. Predict analytically where the spectral peaks occur and their heights, and explain why the spectrum is so clean.
Analytical prediction. The digital frequency is $\omega_0 = 2\pi f/F_s = 2\pi\cdot 5/100 = 2\pi\cdot\frac{5}{100}$, i.e. exactly $k_0 = 5$ periods fit in the $N=100$ window — the tone is on-grid. From Example 8-2: $$X[k] = \frac{N}{2}\delta[((k-5))_{100}] + \frac{N}{2}\delta[((k+5))_{100}] \;\Longrightarrow\; |X[5]| = |X[95]| = 50, \text{ all other bins } 0.$$ The spectrum is clean (no leakage) precisely because the observation window holds an integer number of periods; if $f$ were, say, 5.3 Hz, the line would leak into all bins. The IDFT matrix $\mathbf{W}^{*}/N$ must reconstruct $x[n]$ to machine precision since $\mathbf{W}^{-1} = \mathbf{W}^{*}/N$ exactly.
Cleaned-up MATLAB code:
clc; clear; close all;
% Signal: 5 Hz cosine, sampled at 100 Hz for 1 s
Fs = 100; T = 1/Fs;
t = 0:T:1-T;
f = 5;
x = cos(2*pi*f*t);
% (a) DFT via DFT matrix
N = length(x);
n = 0:N-1; k = 0:N-1;
W = exp(-1j*2*pi/N); % twiddle factor W_N
DFT_matrix = W .^ (n' * k); % [W_N]^(nk), N x N
X_a = DFT_matrix * x.'; % X[k]
% (b) IDFT via matrix: W^(-1) = conj(W)/N
IDFT_matrix = conj(DFT_matrix) / N;
x_a = IDFT_matrix * X_a; % reconstructed x[n]
% (c)-(d) Same with fft / ifft
X_c = fft(x);
x_c = ifft(X_c);
% (e) Stem plots
figure;
subplot(2,2,1); stem(k, abs(X_a), 'filled','b');
title('|X[k]| (DFT matrix)'); xlabel('k'); ylabel('|X[k]|');
subplot(2,2,2); stem(n, real(x_a),'filled','b');
title('reconstructed x[n] (IDFT matrix)'); xlabel('n'); ylabel('x[n]');
subplot(2,2,3); stem(k, abs(X_c), 'filled','b');
title('|X[k]| (fft)'); xlabel('k'); ylabel('|X[k]|');
subplot(2,2,4); stem(n, real(x_c),'filled','b');
title('reconstructed x[n] (ifft)'); xlabel('n'); ylabel('x[n]');
% Checks
max(abs(X_a.' - X_c)) % matrix DFT vs fft : ~1e-12
max(abs(x_a.' - x)) % reconstruction err : ~1e-14
Result (regenerated numerically): peaks of height $50.0000$ at $k = 5$ and $k = 95$, all other bins at round-off level; maximum reconstruction error $\approx 3.6\times 10^{-14}$.
Bin-to-Hz mapping: $f_k = k F_s / N = k\cdot 100/100 = k$ Hz, so bin 5 is literally 5 Hz, and bin 95 represents $-5$ Hz (i.e. $95 - 100$). With fftshift the two lines would sit symmetrically at $\pm 5$ Hz.