Tag Archives: linear algebra

teaching

Two Tricky Linear Algebra Problems


There are a couple questions from the homework that seem to have given people (myself included) a fair amount of trouble. Since I wasn’t able to give satisfactory answers to these questions in office hours, I thought I’d write up clean solutions to the problems, available here. The questions both involve projections \(E : V \to V\) where \(V\) is an inner product space. The problems ask you to prove:

  1. If \(E\) is idempotent (\(E^2 = E\)) and normal (\(E^* E = E E^*\)), then \(E\) is self-adjoint (\(E = E^*\)).
  2. If \(E\) satisfies \(\|E v\| \leq \|v\|\) for all \(v \in V\), then \(E\) is an orthogonal projection onto its image.
computer science expository math

Factor Characterization of Matrix Rank


I am currently taking a course on communication complexity with Alexander Sherstov. Much of communication complexity involves matrix analysis, so yesterday we did a brief review of results from linear algebra. In the review, Sherstov gave the following definition for the rank of a matrix \(M \in \mathbf{F}^{n \times m}\):
\[
\mathrm{rank}(M) = \min\{k | M = A B, A \in \mathbf{F}^{n \times k}, B \in \mathbf{F}^{k \times m}\}
\]
Since this “factor” definition of rank appears very different from the standard definition given in a linear algebra course, I thought I would prove that the two definitions are equivalent.

The “standard” definition of rank is
\[
\mathrm{rank}(M) = \mathrm{dim}\ \mathrm{span} \{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_m\}
\]
where \(\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_m\) are the columns of \(M\). Equivalently, \(\mathrm{rank}(M)\) is the number of linearly independent columns of \(M\).

An easy consequence of the standard definition of rank is that the rank of a product of matrices is at most the rank of the first matrix: \(\mathrm{rank}(A B) \leq \mathrm{rank}(A)\). Indeed, the columns of \(AB\) are linear combinations of the columns of \(A\), hence the span of the columns of \(AB\) is a subspace of the span of the columns of \(A\). Thus, if we can write \(M = A B\) with \(A \in \mathbf{F}^{n \times k}\) and \(B \in \mathbf{F}^{k \times m}\), we must have \(\mathrm{rank}(M) \leq k\).

It remains to show that if \(\mathrm{rank}(M) = k\) then we can factor \(M = A B\) with \(A \in \mathbf{F}^{n \times k}\) and \(B \in \mathbf{F}^{k \times m}\). To this end, assume without loss of generality that the first \(k\) columns of \(M\) are linearly independent. Write these columns as vectors
\(\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k\). Denote the remaining columns by \(\mathbf{w}_1, \mathbf{w}_2, \ldots, \mathbf{w}_{m-k}\). Since these vectors lie in the span of the first \(k\) columns of \(M\), we can write the \(\mathbf{w}_j\) as linear combinations of the \(\mathbf{v}_i\):
\[
\mathbf{w}_j = \sum_{i = 1}^k b_{i, j} \mathbf{v}_i \quad\text{for}\quad j = 1, 2, \ldots, m – k.
\]
Now define the matrices
\[
A = (\mathbf{v}_1\ \mathbf{v}_2\ \cdots\ \mathbf{v}_k)
\]
and
\[
B = (\mathbf{e}_1\ \mathbf{e}_2\ \cdots\ \mathbf{e}_k\ \mathbf{b}_1\ \mathbf{b}_2\ \cdots\ \mathbf{b}_{m – k})
\]
where \(\mathbf{e}_j\) is the \(j\)th standard basis vector in \(\mathbf{F}^k\) and
\[
\mathbf{b}_j =
\begin{pmatrix}
b_{1, j}\\
b_{2, j}\\
\vdots\\
b_{k, j}
\end{pmatrix}
\quad\text{for}\quad j = 1, 2, \ldots, m – k.
\]
It is straightforward to verify that we have \(M = A B\), which proves the equivalence of the two definitions of rank.