How do the rows of a change of basis matrix form a basis for expressing columns?

I am reading this article on Principal Component Analysis (PCA) and in section III-B (page 3) it has strange definition I don't understand.

In the toy example $\mathbf{X}$ is an $m \times n$ matrix.... Let $\mathbf{Y}$ be another $m \times n$ matrix related by a linear transformation $\mathbf{P}$. $\mathbf{X}$ is the original recorded data set and $\mathbf{Y}$ is a re-representation of that data set.

$$\mathbf{P} \mathbf{X} = \mathbf{Y} \tag{1}$$

Also let us define the following quantities.

• $\mathbf{p}_i$ are the rows of $\mathbf{P}$.
• $\mathbf{x}_i$ are the columns of $\mathbf{X}$ (or individual $\vec{X}$).
• $\mathbf{y}_i$ are the columns of $\mathbf{Y}$.

Equation 1 represents a change of basis and thus can have many interpretations.

1. $\mathbf{P}$ is a matrix that transforms $\mathbf{X}$ into $\mathbf{Y}$.
2. Geometrically $\mathbf{P}$ is a rotation and a stretch whcih again transforms $\mathbf{X}$ into $\mathbf{Y}$.
3. The rows of $\mathbf{P}$, $\{ \mathbf{p}_1, \ldots , \mathbf{p}_m \}$, are a set of new basis vectors for expressing the columns of $\mathbf{X}$.

I do not understand this last part, how the rows $\mathbf{p}_i$ of $\mathbf{P}$ are a set of new basis vectors for expressing the columns of $\mathbf{X}$.

The reason I don't understand latter part is that change of basis matrix usually has basis in its columns, not rows. Then multiplying by column vector on the right we get combination of matrix's columns, which is exactly representation in new basis.

So I would expect new basis to be in columns of $\mathbf{P}$, not rows of $\mathbf{P}$. What am I missing here?

• Did you read on? Tries to explain it. – Berci Jul 19 '15 at 22:13
• @Berci: I did, many times :) I'm obviously missing something here - the columns and rows of P can't both be basis vectors – zlatanski Jul 19 '15 at 22:16
• @Berci: I guess unless P is orthogonal, in which case we can look at it as transpose of $P^{-1}$ – zlatanski Jul 19 '15 at 22:26

Your confusion is understandable and may perhaps lead you to a deeper understanding of vectors and matrices.

The problem is that we tend to treat vectors and matrices as just rows and arrays of numbers, without clearly differentiating between different roles they play. In the scenario you're thinking of, you have columns that play the role of vectors in a vectors space, and you multiply them by a column vector of coefficients. In that case, that column vector isn't being considered as a vector in a vector space; it's just a convenient grouping of numbers that allows you to succinctly express a linear combination of the column vectors on the left, yielding a vector in their vector space as a product without having to write a sum for the linear combination.

By contrast, in the text you're reading, the columns of $\mathbf X$ aren't coefficients but vectors of data. The multiplication by $\mathbf P$ isn't meant to form a linear combination (neither of coefficients in $\mathbf P$ with vectors in $\mathbf X$, nor of coefficients in $\mathbf X$ with vectors in $\mathbf P$), but to analyze the data in $\mathbf X$, and the result is a vector of coefficients. The article goes on to say in Section D on p. 5: "PCA assumes $\mathbf P$ is an orthonormal matrix." (Rather bad style to say that there and not at the point where you're reading.) That means that you can consider it as constituting an orthonormal basis, and multiplying it onto a vector analyzes that vector into its coefficients in that basis.

So despite the superficial similarity of multiplying a vector by a matrix, this is a very different operation than the one you're thinking of – instead of multiplying a vector of coefficients with a matrix of basis vectors to get a linear combination living in the same vector space as the basis vectors, in this case you're multiplying a vector that lives in a vector space with a matrix representing an orthonormal basis to get a vector of coefficients.

• This looks like an excellent answer I still have to study, thanks! A clarifying question about the second paragraph. In the scenario I was thinking of, why is the component vector multiplying a matrix of base vectors (in its columns) "does not live in a vector space", though? Doesn't it, really? I would expect such a "list of components" to fulfill all requirements of a vector space – zlatanski Jul 19 '15 at 22:55
• @zlatanski: Yes, formally it fulfills the requirements of a vector space, and sometimes it can indeed be useful to consider vectors of coefficients as vectors in their own right -- which is part of why we use the same notation for them and easily confuse them. Perhaps it was a bit misleading of me to write "that lives in a vector space" -- you're right that the coefficient vector can also be considered to "live in a vector space" -- but that's not its role in this operation; it's not something that we're forming linear combinations of or finding coefficients of in this operation. – joriki Jul 19 '15 at 23:04
• Also, would it be correct to say that without assuming an orthogonal P, the claims in section III-B of the article are imprecise? – zlatanski Jul 19 '15 at 23:07
• @zlatanski: Yes, I'd agree with that. If a matrix isn't orthogonal, you can't use it to analyze a vector into coefficients. You'd have to use its inverse -- which is the transpose in the case of an orthogonal matrix. (By the way, in a sense that turns the basis vectors back into column vectors as you'd expected -- column vectors that have been transposed to row vectors in order to invert them in order to use them to analyze a vector into coefficients.) – joriki Jul 19 '15 at 23:10
• Thank you! This actually makes total sense. If $P$ is orthonormal then $P^T=P^{-1}$, meaning that we got $P^{-1}X$, so if $P$ consists of basis vectors in its columns, $Y$ becomes the components of $X$ in that basis. So it just reduces to the "classical" change of basis matrix (where the components transform contravariantly, as always) – zlatanski Jul 19 '15 at 23:27

This part is awfully explained in this article, but after some confusion eventually I came to following conclusions:

1) In the case of PCA we assume that our initial basis in which our data $X$ is expressed is identity matrix $I$ (which is orthonormal)

2) Then we apply following change of basis theorem( I am not going to prove this):

If P is a transition matrix from an orthonormal basis to another orthonormal basis,then P is orthogonal

3) In PCA data we assume that our new basis in which we will express our data is also orthonormal

4) Next theorem(easy to prove):

If A is an identity basis and B is our new basis, then change of basis matrix $P$ (from A to B): $P=B$

5)As a result of above theorems we can conclude that if we want to change orthonormal identity basis $A$ to some other orthonormal basis $B$, we have following properties: $$P=B$$ $$P^{-1}=P^{T}$$ $$B^{T}=P^{T}$$

6) So rows of our transformation matrix $P^{-1}=B^{T}$ from $A$ to $B$ are the columns(basis vectors) of our new orthonormal basis $B$. And this is fully consistent with PCA tutorial article.

This statement confused me too; here's the most intuitive way I can understand it.

Note that each column of $$\textbf{X}$$, $$x_i$$, is the representation of $$x_i$$ in $$\mathbb{R}^m$$ which we have expanded in the standard basis, (1,0,0..0), (0,1,0...0) etc. The rows of $$\textbf{P}$$, which is m by m, are also representations of vectors in $$\mathbb{R}^m$$, $$p_i$$, also in terms of the standard basis for $$\mathbb{R}^m$$. Our goal is to find a representation of $$x_1$$(and in general $$x_i$$) as a linear combination of the vectors $$p_i$$(so that we've represented the columns of $$\textbf{X}$$ in terms of the rows of $$\textbf{P}$$, as the article states we can). I'm going to use $$p_i$$ to mean the ith row of $$\textbf{P}$$ and to mean the vector it represents(in general these are different but in this case they're confusingly essentially equivalent; they are both m-tuples of real numbers).

We assume $$\textbf{P}$$ is orthonormal. Since $$\textbf{P}$$ is orthonormal by definition its rows are orthonormal, meaning if we take any two rows $$p_i$$ and $$p_j$$ where i and j are different, then their dot product is 0, and if i and j are the same then their dot product is 1.

It's a fact that orthonormality implies independence, so the $$p_i$$ are independent. Since the $$p_i$$ are independent and we have m of them, by linear algebra they form a basis for $$\mathbb{R}^m$$. Therefore given any vector in $$\mathbb{R}^m$$, say $$x_1$$, we can write it as a linear combination of the $$p_i$$, say it is $$x_1 = \sum_{j=1}^{m} c_jp_j$$. Our goal from the start has been to determine these $$c_j$$.

If we take the dot product of the sum above with $$p_1$$, then we see that by using linearity of the dot product and orthonormality of the $$p_i$$ that we have $$p_1 \cdot x_1 = c_1$$. Similarly, if we take the dot product of the sum with $$p_i$$, then we have $$p_i \cdot x_1 = c_i$$. So we've determined the $$c_i$$, they are the dot products of $$p_i$$ with $$x_i$$. But this is exactly the first column of the matrix $$\textbf{Y}$$, $$y_1$$, which we can see by looking at $$\textbf{P} \textbf{X} = \textbf{Y}$$, and finding the entries of $$y_1$$ by row-column multiplication.

The other representations of the $$x_i$$ in the $$p_j$$ basis are similarly found to be exactly the columns of $$\textbf{Y}$$. Hope this helps.