Monthly Archives: October 2014

computer science expository math musings

The Aura of Interactive Proofs


In his essay The Work of Art in the Age of Mechanical Reproduction, Walter Benjamin introduces the idea that original artwork has an aura — some ineffable something that the work’s creator imbues into the work, but which is lost in reproductions made by mechanical means. There is something unique about an original work. Let us imagine that Walter is able to read the aura of work of art, or sense its absence. Thus, he has the seemingly magical ability to tell original art from mechanical forgery.

Andy Warhol is skeptical of Walter’s claims. Andy doesn’t believe in the aura. And even if the aura does exist, he sincerely doubts that Walter is able to detect its presence. In an attempt to unmask Walter for the fraud he undoubtedly he is, Andy hatches a cunning plan to catch Walter in a lie. By hand, he paints an original painting, then using the most advanced technology available, makes a perfect replica of the original. Although the replica looks exactly like the original to the layman (and even Andy himself), according to Walter, there is something missing in the replica.

Andy’s original plan was to present Walter with the two seemingly identical paintings and simply ask which is the original. He soon realized, however, that this approach would be entirely unsatisfactory for his peace of mind. If Walter picked the true original, Andy still couldn’t be entirely convinced of Walter’s powers: maybe Walter just guessed and happened to guess correctly! How can Andy change his strategy in order to (1) be more likely to catch Walter in his lie (if in fact is he lying) and (2) be more convinced to Walter’s supernatural abilities if indeed he is telling the truth?

read more »

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.

expository game theory

The Game Theory of (Anti) Vaccination


I recently read an article about the prevalence of parents not vaccinating their children in certain (read: affluent) LA communities. While I vehemently disagree with the anti-vaccination movement, there are certain game-theoretic incentives that might compel people not to vaccinate. The idea is very closely related to the prisoner’s dilemma–one of the most studied scenarios in game theory.

Imagine that you do believe that vaccines had the potential to cause harm. Maybe not everyone vaccinated is harmed by the vaccine, but you believe there is a chance that the vaccine itself will cause some malady. Let’s quantify the (perceived) harm caused by vaccination to be say, \(4\) harm units. If an otherwise rational person chooses not vaccinate, it is probably because the perceived harm done by the vaccine is greater than the perceived harm from the disease the vaccine is meant to prevent. So let’s quantify the (anticipated) harm caused by not vaccinating to be, say, \(1\) harm unit. In this (overly simplified and probably inaccurate) world, any reasonable person would choose no vaccine (\(1\) harm unit) over vaccination (\(4\) harm units).

Here is the problem: by not vaccinating your own children, you put the entire rest of the population at a greater risk of the disease. We can formalize this as follows. Assume there is a population of \(n\) people, each of whom chooses either a vaccine or no vaccine. A person who gets vaccinated incurs \(4\) harm units, but if a person chooses not be vaccinated, the entire population of \(n\) people incur \(1\) harm unit.

Bob is deciding whether or not to vaccinate. Regardless of Bob’s choice, some people will vaccinate, while others will not. Suppose \(k\) people choose not to vaccinate. Then every person incurs \(k\) harm units from those people. Thus, if Bob chooses to vaccinate, he will incur \(k + 4\) harm units (while each non-vaccinator incurs \(k\)), but if he chooses not to, he will only incur \(k + 1\) harm units (as will the other non-vaccinators). Thus, Bob has an incentive to not vaccinate. Bob is no martyr (in fact, he is downright selfish) so he decides not to vaccinate.

What is interesting about this scenario, is that any individual can improve their own situation (i.e., incur less harm) by selfishly choosing not to vaccinate. But if everyone (or even more than \(4\) people) choose not to vaccinate, everyone is worse off than if they had all chosen to vaccinate. In fact, if everyone acts in their own best interest, everyone achieves the worst possible outcome!