Math 511: Linear Algebra
Linear Systems with MATLAB
Chapter One, Problem Set 1.P3 — Honors Option
Each section and exercise title is a link. At the end of each section there is a link back to this table.
- Introduction
- 1.P3.1 Matrices, Vectors, and Built-in Functions
- 1.P3.2 The Colon Operator
- 1.P3.3 Submatrices and Slicing
- 1.P3.4 Solving and Verifying a Linear System
- 1.P3.5 Exercises
- Exercise 1 - Fitting a Linear Model (Statistical Modeling)
- Exercise 2 - The Redundant Feature (Machine Learning)
- Exercise 3 - Aliasing in a Sampled Signal (Speech and Signal Processing)
- Exercise 4 - A Fragile Recovery Problem (Data Engineering)
- Exercise 5 - Affine Registration of Two Images (Computer Vision)
- Exercise 6 - Additive Bias Model (Recommender Systems)
- Exercise 7 - Reconstructing a Suppressed Table (Data Privacy)
- Exercise 8 - Throughput in a Data Pipeline (Data Engineering)
- Exercise 9 - Short Answer
- copyleft
Introduction 
Computational Linear Algebra¶
This is Problem Set 1.P3, the first of the two honors options for Chapter One; Problem Set 1.P4, Formalism and Proof, is the second. It uses 
Sections 1.P3.1 through 1.P3.4 teach the MATLAB you need. Work the practice exercises in those sections before starting the assigned exercises; solutions to the practice exercises are included.
A Note to the Student¶
The exercises in section 1.P3.5 are independent of one another. Your instructor will assign a subset chosen to match your internship, research area, or major interest. Each exercise carries a label naming the field it comes from. You are welcome to work the others on your own.
Answer all parts of each assigned exercise in order in a single pdf document. Include the MATLAB commands you used and their output. In MATLAB you may record a session with the diary command, or use the Live Editor and export to pdf. A numerical answer with no supporting commands earns no credit; the point of the exercise is the reasoning that connects the commands to the linear algebra.
1.P3.1 Matrices, Vectors, and Built-in Functions
Everything is a Matrix¶
MATLAB stores every quantity as a matrix. A scalar is a $1\times 1$ matrix and a vector in $\mathbb{R}^n$ is an $n\times 1$ matrix. You enter a matrix inside square brackets, separating the entries in a row with spaces or commas and separating rows with semicolons. A statement ending in a semicolon suppresses the printed output, which matters when a matrix is large.
A = [1 2 0 -1; 5 4 -6 1; 0 4 4 -4; 2 1 -3 1]
b = [-3; -9; -4; -3]
size(A)
The transpose operator is the apostrophe, so b = [-3 -9 -4 -3]' produces the same column vector. For matrices with real entries the apostrophe is the transpose $A^T$ of Chapter One.
Definition¶
Array Construction and Reduction Functions
$$ \begin{array}{|l|l|} \hline \textbf{Command} & \textbf{Result} \\ \hline \texttt{zeros(m,n)} & \text{an } m\times n \text{ matrix of zeros} \\ \hline \texttt{ones(m,n)} & \text{an } m\times n \text{ matrix of ones} \\ \hline \texttt{eye(n)} & \text{the } n\times n \text{ identity matrix } I_n \\ \hline \texttt{rand(m,n)} & \text{entries drawn uniformly from } (0,1) \\ \hline \texttt{randn(m,n)} & \text{entries drawn from a standard normal distribution} \\ \hline \texttt{randi([a b],m,n)} & \text{entries drawn uniformly from the integers } a, a+1, \ldots, b \\ \hline \texttt{floor(X)} & \text{each entry rounded down to an integer} \\ \hline \texttt{triu(X)},\ \texttt{tril(X)} & \text{the upper or lower triangular part of } X \\ \hline \texttt{sum(X)} & \text{a row vector of column sums} \\ \hline \texttt{sum(X,2)} & \text{a column vector of row sums} \\ \hline \texttt{size(X)},\ \texttt{numel(X)} & \text{the dimensions, and the number of entries} \\ \hline \texttt{abs(X)},\ \texttt{max(X)},\ \texttt{norm(v)} & \text{absolute values, largest entry, length of a vector} \\ \hline \texttt{format long},\ \texttt{format short} & \text{display 15 digits, or 5 digits} \\ \hline \end{array} $$
The expression randi([0 9],6,6) produces a $6\times 6$ matrix whose entries are integers from $0$ to $9$, and randi([0 9],6) produces the same thing for a square matrix. Integer test matrices are far easier to check by hand than decimal ones, so this idiom appears throughout the exercises.
Older MATLAB code, including most linear algebra textbooks written before 2010, builds the same matrix with floor(10*rand(6)), because randi was not added to the language until R2008b. The two produce the same distribution. Prefer randi, which says what it means, but learn to recognize the older form when you read published code.
The second argument to sum is the dimension along which the sum is taken, and this trips up nearly everyone the first time. sum(X) adds down the columns, producing a row vector. sum(X,2) adds across the rows, producing a column vector. When you are unsure which one you want, run both on a small matrix and look at the shape of the answer.
Practice Exercise 1 - Enter a Linear System¶
Enter the coefficient matrix and constant vector of the linear system
$$ \begin{bmatrix} \ \ 3\ &\ \ 2\ & -1\ \\ \ \ 1\ & -1\ &\ \ 2\ \\ \ \ 2\ &\ \ 1\ &\ \ 1\ \end{bmatrix}\mathbf{x} = \begin{bmatrix}\ \ 4\ \\ \ \ 3\ \\ \ \ 5\ \end{bmatrix} $$
into MATLAB. Report the size of the coefficient matrix, and verify that $\mathbf{x} = (1,\ 2,\ 2)^T$ is not a solution by computing the residual vector $\mathbf{b} - A\mathbf{x}$.
View Solution
A = [3 2 -1; 1 -1 2; 2 1 1];
b = [4; 3; 5];
size(A)
x = [1; 2; 2];
r = b - A*x
The command size(A) reports 3 3, so this is a square $3\times 3$ system. The residual is
$$ \mathbf{b} - A\mathbf{x} = \begin{bmatrix}\ \ 4\ \\ \ \ 3\ \\ \ \ 5\ \end{bmatrix} - \begin{bmatrix}\ \ 3\ \\ \ \ 4\ \\ \ \ 6\ \end{bmatrix} = \begin{bmatrix}\ \ 1\ \\ -1\ \\ -1\ \end{bmatrix} \neq \mathbf{0} $$
Since the residual is not the zero vector, the vector $\mathbf{x}$ does not satisfy the system. A residual is the standard way to check a claimed solution: it requires no elimination and it works for rectangular systems as well as square ones.
1.P3.2 The Colon Operator
The Most Important Operator in MATLAB¶
The colon operator builds a row vector of evenly spaced values. It is the single most useful piece of MATLAB syntax, and it appears in almost every line of code that touches a matrix.
1:6 % the row vector [1 2 3 4 5 6]
0:2:10 % start 0, step 2, stop at or before 10
10:-1:1 % counting down
(0:7)' % a column vector, because of the transpose
Definition¶
The Colon Operator
The expression first:last produces the row vector
$$ \begin{bmatrix} \text{first} & \text{first}+1 & \text{first}+2 & \cdots \end{bmatrix} $$
containing every value that does not exceed last. The expression first:step:last uses the given increment instead of $1$, and the step may be negative or non-integer. If the step carries you past last immediately, the result is an empty matrix with no entries, which is not an error.
Two properties matter for our work. First, the number of entries in a:h:b is $\lfloor (b-a)/h \rfloor + 1$, not $(b-a)/h$; forgetting the $+1$ is the classic off-by-one error. Second, arithmetic applies to the whole vector at once, so a vector of sample times for a signal recorded at $f_s$ samples per second is written in one line.
fs = 8000; % sampling rate in samples per second
N = 16; % number of samples
t = (0:N-1)'/fs; % a column vector of the 16 sample times
This is how you will build the rows of a data matrix in the exercises that follow, and it is how MATLAB code in signal processing, controls, and time series analysis is written in practice.
The Colon Operator and linspace¶
MATLAB offers a second way to build an evenly spaced vector. The command linspace(a,b,n) returns $n$ points beginning at $a$ and ending at $b$. It is tempting to treat the two as interchangeable and write
linspace(a, b, floor((b-a)/h)+1) % NOT the same as a:h:b in general
but the two agree only when $h$ divides $b-a$ exactly. The difference is worth understanding, because the two commands control different quantities.
$$ \begin{array}{|l|l|l|} \hline \textbf{Command} & \textbf{You control} & \textbf{MATLAB determines} \\ \hline \texttt{a:h:b} & \text{the first value and the step } h & \text{the count, and where the vector stops} \\ \hline \texttt{linspace(a,b,n)} & \text{both endpoints and the count } n & \text{the step, which is } (b-a)/(n-1) \\ \hline \end{array} $$
Take $a = 0$, $b = 1$, and $h = 0.3$. The colon operator produces four values,
$$ \texttt{0:0.3:1} \longrightarrow \begin{bmatrix} 0 & 0.3 & 0.6 & 0.9 \end{bmatrix} $$
stopping at $0.9$ because $1.2$ would exceed $b$. The formula above asks for $\lfloor 1/0.3 \rfloor + 1 = 4$ points, and linspace(0,1,4) produces
$$ \begin{bmatrix} 0 & \frac{1}{3} & \frac{2}{3} & 1 \end{bmatrix} $$
The counts match, but the spacing is $\frac{1}{3}$ rather than $0.3$, and the last value is $1$ rather than $0.9$. Neither vector is wrong; they answer different questions.
Which One for Sample Times?¶
Use the colon operator whenever the step is the quantity that carries meaning. Sample times are the leading case: the spacing must be exactly $1/f_s$, because the sampling rate is a physical property of the recording device and every frequency computation depends on it. Writing t = (0:N-1)'/fs fixes the step by construction and lets the recording end where it ends.
Building sample times as linspace(0, T, N) instead forces the last sample to land exactly on $T$, which silently changes the spacing to $T/(N-1)$ and therefore changes the sampling rate to something other than $f_s$. The vector still looks entirely reasonable. The error surfaces much later as frequencies that come out slightly wrong, and it is a genuinely common bug in student signal processing code.
Use linspace when the endpoints are what matter and the spacing does not, as when you want exactly $200$ points across an interval to draw a smooth curve.
Practice Exercise 2 - Sample Times¶
A sensor records at $f_s = 500$ samples per second for one quarter of a second.
(a) Write one MATLAB statement that builds a column vector $\mathbf{t}$ of the sample times, beginning at $t = 0$.
(b) How many samples are recorded? Predict the number before you run numel(t).
(c) Write a statement that builds the column vector of values of $f(t) = 3t + 1$ at those sample times.
(d) A classmate builds the same sample times with linspace(0, 0.25, 125). Compute the spacing of that vector and compare it with $1/f_s$. What sampling rate does the classmate's vector actually represent?
View Solution
(a) One quarter of a second at $500$ samples per second is $125$ sampling intervals, and the last sample time is $124/500$.
fs = 500;
t = (0:124)'/fs;
Writing t = (0:0.002:0.248)' also works, but building the index range first and dividing by fs is far less error-prone.
(b) The vector 0:124 contains $124 - 0 + 1 = 125$ entries, so $125$ samples are recorded. Note that $125$ samples span only $124$ intervals; a quarter second of recording starting at $t=0$ does not include the sample at $t = 0.25$.
(c) Arithmetic on a vector is applied entrywise.
f = 3*t + 1;
(d) The classmate's vector has $125$ points spanning the closed interval from $0$ to $0.25$, so its spacing is
$$ \frac{0.25 - 0}{125 - 1} = \frac{0.25}{124} \approx 0.0020161 $$
while the correct spacing is $1/500 = 0.002$ exactly.
tc = linspace(0, 0.25, 125)';
dt = tc(2) - tc(1)
1/dt
The reciprocal of the spacing is about $496$, so the classmate's vector represents a sampling rate of $496$ samples per second rather than $500$. Nothing about the vector looks wrong, and every subsequent frequency computation is off by nearly one percent. Asking linspace for $125$ points from $0$ to $0.25$ forces the last sample to land on $0.25$, and the $125$ samples then span $124$ intervals rather than the $125$ intervals of a quarter second at $500$ samples per second.
1.P3.3 Submatrices and Slicing
Reading and Writing Submatrices¶
Section 1.2.4 of the notes defined a submatrix as the matrix obtained by deleting rows or columns from a matrix. MATLAB gives you these submatrices directly through index expressions, and this is how you will assemble augmented matrices, extract solution vectors, and modify a single column of a coefficient matrix.
Definition¶
Index Expressions
For a matrix $X$ with $m$ rows and $n$ columns,
$$ \begin{array}{|l|l|} \hline \textbf{Expression} & \textbf{Result} \\ \hline \texttt{X(i,j)} & \text{the single entry } x_{ij} \\ \hline \texttt{X(i,:)} & \text{row } i \text{ of } X \\ \hline \texttt{X(:,j)} & \text{column } j \text{ of } X \\ \hline \texttt{X(1:3,2:4)} & \text{the submatrix of rows 1 through 3 and columns 2 through 4} \\ \hline \texttt{X([1 3 5],:)} & \text{rows 1, 3 and 5, in that order} \\ \hline \texttt{X(:,end)} & \text{the last column} \\ \hline \texttt{X(:,j) = v} & \text{overwrite column } j \text{ with the vector } \mathbf{v} \\ \hline \texttt{X(:,j) = []} & \text{delete column } j \text{ entirely} \\ \hline \texttt{[A b]} & \text{the augmented matrix } [\,A \mid \mathbf{b}\,] \\ \hline \end{array} $$
Used by itself, the colon means every index in that position. MATLAB indices begin at $1$, matching the subscripts $a_{ij}$ of the notes.
Indices appear on both sides of an assignment. Reading U(:,end) extracts the constant column of an augmented matrix in reduced row echelon form; writing A(:,3) = A(:,1:2)*[4; 3] replaces the third column of $A$ with $4\mathbf{a}_1 + 3\mathbf{a}_2$, a matrix-vector product that produces a linear combination of the first two columns. That second statement is worth studying, because it is how you deliberately build a matrix with a dependent column.
Practice Exercise 3 - Build a Design Matrix¶
A design matrix in statistics has one row per observation and one column per model coefficient. A model with an intercept term has a leading column of ones. Suppose the measured features are stored in
F = [10 8; 5 10; 15 5; 8 9];
(a) Build the design matrix $X = [\,\mathbf{1}\ \ F\,]$ whose first column is a column of ones.
(b) Extract the third observation as a row vector.
(c) Extract the second feature, for all four observations, as a column vector.
View Solution
(a) The number of rows must match, so build the column of ones from size(F,1) rather than typing 4. Code that reads its dimensions from the data keeps working when the data changes.
n = size(F,1);
X = [ones(n,1) F]
$$ X = \begin{bmatrix} 1 & 10 & 8 \\ 1 & 5 & 10 \\ 1 & 15 & 5 \\ 1 & 8 & 9 \end{bmatrix} $$
(b) X(3,:) returns the row vector $\begin{bmatrix} 1 & 15 & 5\end{bmatrix}$.
(c) The second feature sits in column three of $X$, because the intercept occupies column one. Either X(:,3) or F(:,2) returns $(8,\ 10,\ 5,\ 9)^T$.
Practice Exercise 4 - Manufacture a Singular Matrix¶
Random matrices are almost never singular, so a singular test matrix must be built on purpose. Enter
A = randi([0 9],6,6);
A(:,6) = -sum(A(:,1:5),2);
(a) Describe in words what the second statement does.
(b) Explain why the resulting matrix must be singular. Name a nonzero vector $\mathbf{x}$ with $A\mathbf{x} = \mathbf{0}$.
(c) Confirm your answer by computing rref(A) and by computing $A\mathbf{x}$ for your vector.
View Solution
(a) sum(A(:,1:5),2) adds across the rows of the submatrix formed by the first five columns, producing a $6\times 1$ vector whose $i$th entry is $a_{i1}+a_{i2}+\cdots+a_{i5}$. The statement overwrites column six with the negative of that vector.
(b) After the assignment every row of $A$ sums to zero:
$$ a_{i1} + a_{i2} + \cdots + a_{i5} + a_{i6} = a_{i1} + \cdots + a_{i5} - (a_{i1} + \cdots + a_{i5}) = 0 $$
Each row sum is exactly the entry of $A\mathbf{x}$ for $\mathbf{x} = (1,1,1,1,1,1)^T$, so $A\mathbf{x} = \mathbf{0}$ with $\mathbf{x} \neq \mathbf{0}$. A square matrix whose homogeneous system has a nontrivial solution is singular, so $A$ is singular no matter which random integers appeared.
(c) With x = ones(6,1), the product A*x is the zero vector. The command rref(A) returns a matrix with five pivot columns and one free column rather than the identity $I_6$, which is the reduced row echelon form of every nonsingular $6\times 6$ matrix.
1.P3.4 Solving and Verifying a Linear System
Two Commands, Two Purposes¶
Definition¶
Solution Commands
$$ \begin{array}{|l|l|} \hline \textbf{Command} & \textbf{Result} \\ \hline \texttt{rref([A b])} & \text{the reduced row echelon form of the augmented matrix} \\ \hline \texttt{[R,p] = rref([A b])} & \text{the form } R \text{ and the list } p \text{ of pivot columns} \\ \hline \texttt{A}\backslash\texttt{b} & \text{a solution of } A\mathbf{x} = \mathbf{b} \text{, computed by elimination} \\ \hline \texttt{b - A*x} & \text{the residual vector, zero exactly when } \mathbf{x} \text{ solves the system} \\ \hline \end{array} $$
The second output of rref is the list of pivot columns, which is exactly the information Chapter One asks you to read off an echelon form: pivot columns give pivot variables, and the remaining columns give free variables.
The two commands answer different questions. The backslash operator returns one vector and tells you nothing about how many solutions exist. The reduced row echelon form tells you everything: whether the system is consistent, how many free variables it has, and what the complete solution set looks like. In this course you use rref to understand the system and the backslash operator to solve it quickly once you understand it.
Reduced Row Echelon Form on Measured Data¶
The reduced row echelon form is defined by exact arithmetic, but MATLAB computes in floating point, where a quantity that should be exactly zero often comes out as $10^{-16}$ instead. The rref command therefore treats any sufficiently small number as zero, and the cutoff it uses depends on the size of the entries in your matrix.
The consequence matters for data work. Two columns that are exactly dependent, such as a duplicated feature, are recognized reliably. Two columns that are dependent only up to measurement noise are not: rref will report a pivot in a column that carries almost no real information. For that reason rref is a tool for understanding the structure of a system, not for drawing conclusions from noisy measurements. The techniques for the noisy case come later in the course.
Practice Exercise 5 - Two Ways to Solve¶
For the system of Practice Exercise 1, compute rref([A b]) and A\b. Explain how the reduced row echelon form shows that the solution is unique, and verify the solution with a residual.
View Solution
A = [3 2 -1; 1 -1 2; 2 1 1];
b = [4; 3; 5];
[R,p] = rref([A b])
x = A\b
r = b - A*x
The reduced row echelon form is
$$ R = \left[ \begin{array}{ccc|c} \ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ \end{array} \right] $$
with pivot list p equal to $\begin{bmatrix} 1 & 2 & 3 \end{bmatrix}$. Every column of the coefficient matrix is a pivot column, so there are no free variables and the system is independent. The last column carries no pivot, so the system is consistent. A consistent independent system has exactly one solution, $\mathbf{x} = (1,\ 1,\ 1)^T$, which is also what the backslash operator returns and what the last column of $R$ displays. The residual b - A*x is the zero vector, confirming the solution.
1.P3.5 Exercises
Choose Your Field¶
The exercises below are independent of one another and may be worked in any order. Each is labeled with the field it comes from, and each reduces to the mathematics of Chapter One. Your instructor will tell you which exercises to submit.
$$ \begin{array}{|l|l|} \hline \textbf{Exercise} & \textbf{Field} \\ \hline \text{1. Fitting a Linear Model} & \text{Statistical Modeling} \\ \hline \text{2. The Redundant Feature} & \text{Machine Learning, Feature Engineering} \\ \hline \text{3. Aliasing in a Sampled Signal} & \text{Speech and Signal Processing} \\ \hline \text{4. A Fragile Recovery Problem} & \text{Data Engineering, Numerical Analysis} \\ \hline \text{5. Affine Registration of Two Images} & \text{Computer Vision} \\ \hline \text{6. Additive Bias Model} & \text{Recommender Systems} \\ \hline \text{7. Reconstructing a Suppressed Table} & \text{Data Privacy, Official Statistics} \\ \hline \text{8. Throughput in a Data Pipeline} & \text{Data Engineering} \\ \hline \text{9. Short Answer} & \text{All Students} \\ \hline \end{array} $$
Exercise 1 - Fitting a Linear Model
Field: Statistical Modeling.
A linear model predicts an outcome as a linear combination of measured features. An instructor models the end-of-semester score $s$ of a student from weekly hours studied $h$ and days attended out of ten $r$,
$$ s = \beta_0 + \beta_1 h + \beta_2 r $$
and records three students.
| Student | Hours $h$ | Days attended $r$ | Score $s$ |
|---|---|---|---|
| A | 10 | 8 | 86 |
| B | 5 | 10 | 70 |
| C | 15 | 5 | 100 |
(a) Write the linear system for $\beta_0$, $\beta_1$, and $\beta_2$ in the form $X\boldsymbol{\beta} = \mathbf{s}$. Build the design matrix $X$ in MATLAB using ones and the slicing of section 1.P3.3. State the size of the system and whether it is square, overdetermined, or underdetermined.
(b) Compute rref([X s]). Identify the pivot columns and the free columns. Is the system consistent? Is it independent? How many solutions does it have?
(c) Solve the system with the backslash operator and state the fitted model. Verify your coefficients by computing the residual vector $\mathbf{s} - X\boldsymbol{\beta}$.
(d) Use the fitted model to predict the score of a student who studies $12$ hours per week and attends $7$ days. Write the prediction as a matrix-vector product in MATLAB rather than by hand arithmetic.
(e) A fourth student is recorded: $h = 8$, $r = 9$, and $s = 79$. Append this observation to $X$ and to $\mathbf{s}$ and compute the reduced row echelon form of the new augmented matrix. What happens, and what does it mean for the model? Explain what feature of the reduced row echelon form told you the answer.
Three observations and three coefficients produced an exact fit, and the fit was worthless as evidence: a model with as many parameters as data points can reproduce any data whatsoever, including pure noise. The fourth observation revealed the problem immediately. This is why a data scientist holds out data the model has never seen.
Exercise 2 - The Redundant Feature
Field: Machine Learning, Feature Engineering.
An analyst modeling exam scores records, for each student, weekday study hours $d$, weekend study hours $e$, and — because the reporting tool provides it — total study hours $u = d + e$. The model with an intercept is
$$ y = \beta_0 + \beta_1 d + \beta_2 e + \beta_3 u $$
| Student | Weekday $d$ | Weekend $e$ | Total $u$ | Score $y$ |
|---|---|---|---|---|
| A | 10 | 4 | 14 | 70 |
| B | 5 | 6 | 11 | 65 |
| C | 8 | 2 | 10 | 54 |
| D | 12 | 3 | 15 | 71 |
(a) Build the $4\times 4$ design matrix $X$ in MATLAB. Build the fourth column from the second and third columns with a single slicing statement rather than typing the totals by hand.
(b) Compute rref([X y]). List the pivot columns and the free columns. Is the system consistent? How many solutions does it have?
(c) Set the free variable to zero and read a particular solution $\mathbf{w}$ from the reduced row echelon form. Then set the free variable to $1$ in the corresponding homogeneous system and find a nonzero solution $\mathbf{z}$ of $X\mathbf{z} = \mathbf{0}$. Verify with a matrix-vector product that $\mathbf{z}$ really is a solution of the homogeneous system.
(d) Show that $\mathbf{w} + t\mathbf{z}$ is a solution for every real $t$ by computing the residual $\mathbf{y} - X(\mathbf{w} + t\mathbf{z})$ for $t = 3$ and for $t = -7$. Write the complete solution set.
(e) Take $t = 100$ and report the resulting coefficients. The coefficient on weekday hours is now strongly negative. Do the predictions change? Explain what this says about interpreting a fitted coefficient as the effect of its feature.
(f) Remove the redundant column and repeat parts (b) and (c). How many solutions does the reduced system have, and what are the coefficients?
A free column in a design matrix is non-identifiability: the data cannot determine the coefficients even though it determines the predictions perfectly. It arises whenever one feature is a linear combination of others, which happens constantly in practice through totals, percentages that sum to one hundred, and indicator columns for every category of a variable that also has an intercept. Chapter One diagnoses all of these with a single call to rref.
Exercise 3 - Aliasing in a Sampled Signal
Field: Speech and Signal Processing.
A microphone records a sound sampled $f_s$ times per second. A recording made up of a constant offset and two pure tones at known frequencies $f_1$ and $f_2$ has samples
$$ y_k = a_0 + a_1 \cos(2\pi f_1 t_k) + a_2 \cos(2\pi f_2 t_k), \qquad t_k = \frac{k}{f_s}, \quad k = 0, 1, \ldots, N-1 $$
The amplitudes $a_0$, $a_1$, and $a_2$ are unknown, and recovering them from the samples is a linear system: one equation per sample, one unknown per tone.
(a) Let $f_s = 8000$, $N = 8$, $f_1 = 1000$, and $f_2 = 9000$. Build the column vector $\mathbf{t}$ of sample times with the colon operator, then build the $8 \times 3$ matrix $A$ whose columns are the constant column and the two cosine columns. Report the size of the system and state whether it is square, overdetermined, or underdetermined.
(b) Compare the second and third columns of $A$ by computing max(abs(A(:,2)-A(:,3))). What do you find, and why? Use the identity $\cos(\theta + 2\pi k) = \cos\theta$ together with the sample times $t_k = k/f_s$.
(c) Generate a recording from known amplitudes with y = A*[3; 2; 1]. Compute rref([A y]) and identify the pivot and free columns. How many amplitude vectors reproduce this recording exactly? Give two different ones and verify both with residuals.
(d) Replace $f_2 = 9000$ with $f_2 = 3000$ and rebuild $A$. Compute the reduced row echelon form again and solve for the amplitudes with the backslash operator. How many solutions are there now, and why did the change of frequency matter?
(e) The general rule is that frequencies $f$ and $f + f_s$ produce identical samples. Using that rule, name another frequency besides $9000$ Hz whose column would coincide with the $1000$ Hz column at this sampling rate. What sampling rate would you need so that a $9000$ Hz tone and a $1000$ Hz tone could be told apart?
Aliasing is usually taught with pictures of misdrawn waveforms. In linear algebra it is exactly one statement: two columns of the sampling matrix coincide, the matrix has a free column, and the amplitudes are not determined by the recording. Choosing a sampling rate is choosing a matrix whose columns are independent.
Exercise 4 - A Fragile Recovery Problem
Field: Data Engineering, Numerical Analysis.
A processing pipeline has nine stages. For auditing purposes each stage reports not its own count but its count minus the counts of every stage downstream of it,
$$ b_i = x_i - (x_{i+1} + x_{i+2} + \cdots + x_9), \qquad i = 1, 2, \ldots, 9 $$
where $x_i$ is the number of records processed at stage $i$. Recovering the stage counts from the audit report is a linear system $B\mathbf{x} = \mathbf{b}$.
(a) Build the coefficient matrix with B = eye(9) - triu(ones(9),1). Write out its first three rows and confirm that they match the description of the audit report. Explain from the shape of $B$ why the system is nonsingular, without computing anything.
(b) Suppose the report is $\mathbf{b} = (0,0,0,0,0,0,0,0,1)^T$: every stage but the last reports a perfect balance. Build $\mathbf{b}$ with zeros and slicing, solve with the backslash operator, and report $\mathbf{x}$. Describe the pattern in the entries.
(c) Now suppose the ninth stage misreports slightly, changing one entry of the matrix: set B(9,1) = -1/128. Compute $B\mathbf{x}$ for the vector $\mathbf{x}$ you found in part (b). What do you get, and what does that tell you about the modified matrix?
(d) Compute rref(B) for the modified matrix and count the pivot columns. Then compute rref([B b]) for the report $\mathbf{b}$ of part (b). Does the modified system have a solution? Explain what changed.
(e) The change to the matrix was $1/128 \approx 0.008$, less than one percent of a single entry, and it destroyed the problem. Explain in your own words why this matters for a pipeline whose audit counts come from real logging systems, and what you would tell an engineer who proposed to recover stage counts this way.
Nonsingular and trustworthy are not the same property. Chapter One tells you whether a solution exists and whether it is unique; it does not tell you whether the solution means anything when the data carries error. This exercise is the bridge to the numerical linear algebra that governs every real computation on measured data.
Exercise 5 - Affine Registration of Two Images
Field: Computer Vision.
Two photographs of the same flat scene, taken from slightly different positions, are related by an affine transformation: a point $(x,y)$ in the first image corresponds to the point $(u,v)$ in the second, where
$$ \begin{align*} u &= a_1 x + a_2 y + a_3 \\ v &= c_1 x + c_2 y + c_3 \end{align*} $$
Finding the six coefficients from matched pairs of points is called image registration, and it is the first step in panorama stitching, medical image alignment, and optical flow. Each matched pair contributes one equation to the system for $\mathbf{a}$ and one to the system for $\mathbf{c}$, and both systems share the same coefficient matrix.
A vision system matches three landmarks between the images.
| Landmark | $x$ | $y$ | $u$ | $v$ |
|---|---|---|---|---|
| P | 2 | 1 | 5 | 3 |
| Q | 5 | 1 | 11 | 6 |
| R | 2 | 4 | 5 | 12 |
(a) Write the linear system for $\mathbf{a} = (a_1, a_2, a_3)^T$. Build its coefficient matrix $M$ in MATLAB from the landmark coordinates using slicing and ones. Explain why the system for $\mathbf{c}$ has the same coefficient matrix.
(b) Compute rref([M u]) and rref([M v]). State the two coefficient vectors and write the affine transformation explicitly.
(c) Verify both solutions with residuals, then use the transformation to predict where the point $(4,\,3)$ of the first image appears in the second. Compute the prediction as a matrix-vector product.
(d) A different run of the matcher returns three landmarks lying on a line: $(1,1)$, $(2,2)$, and $(3,3)$, mapping to $u$-coordinates $3$, $5$, and $7$. Build the new coefficient matrix and compute its reduced row echelon form. How many pivot columns are there? Is the system consistent? How many affine transformations fit these three matches?
(e) Find a particular solution and a nonzero homogeneous solution for the degenerate case, and describe the complete solution set. Then explain geometrically why three collinear landmarks cannot determine the transformation, and state the condition the matcher must satisfy.
A degenerate configuration in geometry and a free column in linear algebra are the same event described in two languages. Vision systems check for this condition before trusting a registration, and the check is a rank computation on a small matrix built exactly the way you built $M$.
Exercise 6 - Additive Bias Model
Field: Recommender Systems.
Before any modern recommender fits a complicated model, it fits a simple one: a global average $\mu$, a bias $b_u$ for each user, and a bias $c_i$ for each item,
$$ r_{ui} = \mu + b_u + c_i $$
Some users rate everything highly, some films are widely liked, and this model captures both. Two users have rated three films on a five point scale.
| Film 1 | Film 2 | Film 3 | |
|---|---|---|---|
| User 1 | 5 | 3 | 4 |
| User 2 | 4 | 2 | 3 |
The unknown vector is $\mathbf{p} = (\mu,\ b_1,\ b_2,\ c_1,\ c_2,\ c_3)^T$.
(a) Write the six equations and build the $6\times 6$ coefficient matrix $A$ in MATLAB. Each row has a $1$ in the $\mu$ column, a $1$ in the column of the rating user, and a $1$ in the column of the rated film.
(b) Compute rref([A r]). How many pivot columns are there? Is the system consistent? How many solutions does it have? Was the number of solutions predictable from the fact that the system is square?
(c) Find two independent solutions of the homogeneous system $A\mathbf{z} = \mathbf{0}$, one for each free variable. Verify both with a matrix-vector product, and describe in words what each one does to the parameters.
(d) Read a particular solution $\mathbf{w}$ from the reduced row echelon form and write the complete solution set. Verify that $\mathbf{w} + 2\mathbf{z}_1 - 5\mathbf{z}_2$ reproduces the ratings exactly.
(e) The standard repair is to require that the user biases sum to zero and the film biases sum to zero. Append these two equations as rows of the augmented matrix, using slicing rather than retyping the matrix, and solve. How many solutions now? Report $\mu$, the user biases, and the film biases, and interpret them.
(f) Suppose user 2 had rated only films 1 and 2, so that the system has five equations and six unknowns. Without recomputing, predict whether adding the two constraint rows of part (e) is still enough to determine the parameters uniquely. Then check your prediction in MATLAB by deleting the appropriate row.
The shifts in part (c) are called gauge freedoms, and they appear throughout data science: in bias models, in factor models, in the softmax layer of a neural network, where adding a constant to every logit changes nothing. In every case the diagnosis is a nonzero solution of a homogeneous system, and the repair is a normalization constraint appended as an extra row.
Exercise 7 - Reconstructing a Suppressed Table
Field: Data Privacy, Official Statistics.
A statistical agency publishes a table of counts broken down by two categories, but suppresses the individual cells to protect privacy and releases only the row and column totals. A researcher wants to know whether the suppressed cells can be recovered from the published margins. The table has two rows and three columns, and the six suppressed counts are $x_{11}, x_{12}, x_{13}, x_{21}, x_{22}, x_{23}$.
| Column 1 | Column 2 | Column 3 | Row total | |
|---|---|---|---|---|
| Row 1 | * | * | * | 30 |
| Row 2 | * | * | * | 20 |
| Column total | 22 | 18 | 10 | 50 |
(a) Write the five margin equations and build the coefficient matrix $A$ and constant vector $\mathbf{b}$ in MATLAB. Order the unknowns $x_{11}, x_{12}, x_{13}, x_{21}, x_{22}, x_{23}$.
(b) Compute rref([A b]). How many pivot columns and how many free columns are there? Explain why the five equations do not act as five independent constraints.
(c) Write the complete solution set with $x_{22}$ and $x_{23}$ as the free variables. Then state the constraints that a table of counts must satisfy beyond the linear equations.
(d) Impose nonnegativity. Determine the range of values each free variable may take, and state the largest and smallest possible value of the suppressed count $x_{11}$. How many integer tables are consistent with the published margins?
(e) The agency later publishes one more statistic: the combined count for the first two columns of row 1 is $25$. Append this equation and recompute the reduced row echelon form. Which suppressed cells are now determined exactly? Comment on what this says about releasing several summaries of the same data.
Disclosure control is a question about the solution set of an underdetermined linear system. Suppression protects a cell only while a free variable remains and the nonnegativity constraints leave the range wide. Both conditions are read directly off the reduced row echelon form of the augmented matrix.
Exercise 8 - Throughput in a Data Pipeline
Field: Data Engineering.
A streaming system routes records through four services, $A$, $B$, $C$, and $D$. Records enter the system at $A$ at $500$ records per second and at $B$ at $200$ per second, and they leave the system from $C$ at $400$ per second and from $D$ at $300$ per second. Internally the services are connected by one-way channels carrying unknown rates:
$$ \begin{array}{ll} x_1: A \to B & x_4: A \to D \\ x_2: B \to C & x_5: B \to D \\ x_3: D \to C & \end{array} $$
In steady state, no service accumulates records, so at each service the total rate in equals the total rate out.
(a) Write the conservation equation at each of the four services and build the augmented matrix in MATLAB.
(b) Compute rref([A b]). How many pivot columns are there? Explain why four conservation equations do not give four independent constraints.
(c) Write the complete solution set with $x_4$ and $x_5$ as free variables.
(d) A channel cannot carry a negative rate. Impose $x_i \ge 0$ for all five channels and determine the constraints on $x_4$ and $x_5$. What is the smallest possible value of $x_4 + x_5$, and what does it mean operationally?
(e) An engineer proposes to shut down the channel $B \to D$ for maintenance, forcing $x_5 = 0$. Append the equation $x_5 = 0$ to the system, recompute the reduced row echelon form, and determine whether the system can still run. Give the resulting rates if it can, along with any remaining freedom.
(f) Verify one specific solution of part (e) by computing a residual, and explain why the residual check is worth doing even when the reduced row echelon form was computed correctly.
Conservation laws produce a dependent system in every field that uses them: traffic networks, electrical circuits, chemical reactions, and data pipelines. The rank deficiency is not a defect in the model, it is the statement that the total is conserved. The free variables are the operational choices left to the engineer.
Exercise 9 - Short Answer
Field: All Students¶
Answer in your own words, in complete sentences. These questions are about the ideas rather than the computations, and a correct answer requires the vocabulary of Chapter One used precisely.
