I don't understand how to keep track of the basis change as you compute smith normal form. We did an example in lecture where:
$A = \begin{pmatrix} [1] & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ \end{pmatrix}$
Where [1] is the pivot position. The first operations performed were:
$R_2\mapsto R_2 - 5R_1$
$R_3\mapsto R_3 - 9R_1$.
Which then gives: $\begin{pmatrix} 1 & 2 & 3 & 4 \\ 0 & -4 & -8 & -12 \\ 0 & -8 & -16 & -24 \\ \end{pmatrix}$.
He then writes: $U\mapsto V$: Basis of V:
$\begin{pmatrix}
1\\
5\\
9 \\
\end{pmatrix}$
$\begin{pmatrix}
0\\
1\\
0 \\
\end{pmatrix}$
$\begin{pmatrix}
0\\
0\\
1 \\
\end{pmatrix}$.
Afterwards, he column transformations:
$C_2\mapsto C_2 - 5C_1$
$C_3\mapsto C_3 - 9C_1$
$C_4\mapsto C_4 - 4C_1$
Getting
$\begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & -4 & -8 & -12 \\
0 & -8 & -16 & -24 \\
\end{pmatrix}$ and basis of U:
$\begin{pmatrix}
1\\
0\\
0 \\
0\\
\end{pmatrix}$
$\begin{pmatrix}
-2\\
-1\\
0 \\
0 \\
\end{pmatrix}$
$\begin{pmatrix}
-3\\
0\\
1 \\
0 \\
\end{pmatrix}$
$\begin{pmatrix}
-4\\
0\\
0 \\
1 \\ \end{pmatrix}$
and then so on, updating the basis after each step. What I don't understand is how these basis are found after each step.
You can think of the decomposition process as follows: starting with $A_0 = A$, $P_0 = I_3$, and $Q_0 = I_4$, we go from $(A_k,P_k,Q_k)$ to $(A_{k+1},P_{k+1},Q_{k+1})$ in such a way that at all points in the process, we have $A = P_k A_k Q_k$. Note that $P_k$ is a change of basis matrix over the codomain and $Q_k$ is a change of basis matrix over the domain.
On the other hand, note that applying a row-operation to $A$ amounts to computing $RA$ for some invertible matrix $R$. Similarly, applying a column-operation to $A$ amounts to computing $C^{-1}A$ for some invertible matrix $C$.
With all that established, consider the following. We begin with
$$ A = \overbrace{\pmatrix{1&0&0\\0&1&0\\0&0&1}}^{P_0} \overbrace{\begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ \end{pmatrix}}^{A_0} \overbrace{\pmatrix{1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1}}^{Q_0}. $$ Applying your row operations amounts to the multiplication $RA$, where $$ R = \pmatrix{1&0&0\\-5&1&0\\-9&0&1}. $$ Note: to find the matrix corresponding to a certain sequence of row operations, simply apply those operations to the identity matrix. Similarly, the matrix corresponding to a certain sequence of columns operations can be found by applying those operations to an identity matrix.
With that in mind, we have $A = (P_0R^{-1})(RA_0)Q_0$. That is, we can take $P_1 = P_0R^{-1} = R^{-1}$. Note that the inverse of $R$ will be the matrix corresponding to the reverse of the row operations associated with $R$.
Similarly, the column operations applied to $A$ are those corresponding to the matrix $$ C = \pmatrix{1&-2&-3&-4\\0&1&0&0\\0&0&1&0\\0&0&0&1}. $$ With that in mind, we have $$ A = (P_0R^{-1})(RA_0C)(C^{-1}Q_0). $$ That is, our work so far amounts to taking $P_1 = P_0R^{-1} = R^{-1}$, $A_1 = RA_0C$, and $Q_1 = C^{-1}Q_0 = C^{-1}$.
After continuing these process, we will eventually end up with $A_k$ equal to the Smith normal form $A_k = D$, so that $A = P_k D Q_k$ is a Smith normal form decomposition. We will have $P_k = R_1^{-1}R_2^{-1} \cdots R_k^{-1}$ for some sequence of row operations with corresponding matrices $R_1,\dots,R_k$. Similarly, we will have $Q_k = C_k^{-1} \cdots C_2^{-1}C_1^{-1}$.
$P_k$ is a change of basis matrix that takes us to the desired basis from the standard basis. Thus, the columns of $P_k$ are the elements of that basis. $Q_k$ is a change of basis that takes us from the desired basis to the standard basis. Thus, the columns of $Q_k^{-1} = C_1C_2 \cdots C_k$ will be the elements of that basis.