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.

*

*$\mathbf{P}$ is a matrix that transforms $\mathbf{X}$ into $\mathbf{Y}$.

*Geometrically $\mathbf{P}$ is a rotation and a stretch whcih again transforms $\mathbf{X}$ into $\mathbf{Y}$.

*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?
 A: 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 vector 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.
A: 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.
A: 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.
