Finding a matrix representation of the transpose transformation

Define $T : M_{n×n}(\mathbb{R}) → M_{n×n}(\mathbb{R})$ by $T(A) := A^t$.

I know this transformation is linear and just takes a matrix and spits out it's transpose. I also know that the transpose is just a matrix with it's columns and rows swapped; however, I don't know how to form a matrix representation of this transformation for arbitrary $n$.

Any help to get me started would be appreciated!

$\newcommand{\R}{\mathbb R}$ Just write what you would do for any linear transformation: write a basis for $M(n,\R)$ then find the "effect" of the transformation on its elements. In this case you'll formally have to go through an isomorphism between $M(n,\R)$ and $\R^{n^2}$: you want to represent it as a matrix, so it has to multiply some vectors. These vectors will represent the matrix in a given basis.

I'll make an example just in $M(2,\R)$, for the sake of simplicity. A general matrix in this space is $$ M= \begin{pmatrix} a & b \\ c & d \end{pmatrix}. $$ Now, let's choose a basis for the vector space: the obvious (but not the best*) choice is the standard basis $\mathcal S=\{E_{11},E_{12},E_{21},E_{22}\}$ given by $(E_{\mu\nu})_{ij}=\delta_{i\mu}\delta_{j\nu}$, so $$ S=\left\{ \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}, \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix} \right\}. $$ In this basis, the matrix $M$ can be written as $aE_{11}+bE_{12}+cE_{21}+dE_{22}$ so it's easily represented as the vector in $\R^{2^2}=\R^4$ $$ v= \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix}. $$ Now, the transposition (I'll call it $T$) acts on the elements of the basis $\mathcal S$ as follows: $$ T(E_{11})=E_{11},\ T(E_{12})=E_{21},\ T(E_{21})=E_{12},\ T(E_{22})=E_{22}. $$ Therefore the matrix associated with $T$ is just $$ \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}. $$

* The calculations were simple anyway, but there's a nicer way to do it (according to me, of course); it just requires a bit of knowledge a priori. The matrix vector space $M(n,\R)$ is a direct sum of the space $S(n,\R)$ of symmetric matrices and $A(n,\R)$ of antisymmetric ones: $$ M(n,\R)=S(n,\R)\oplus A(n,\R) $$ so a basis of $M(n,\R)$ can be found from these two subspaces. Moreover, $\dim A(n,\R)=\frac12(n-1)n$ and $\dim S(n,\R)=\frac12n(n+1)$.

Now, if $x\in A(n,\R)$ then $T(x)=-x$, and if $y\in S(n,\R)$ then $T(y)=y$, and this is obviously true for the elements of their bases too. So, we form a basis of $M(n,\R)$ consisting of $\frac12n(n+1)$ linearly independent elements from $S(n,\R)$ and $\frac12n(n-1)$ elements from $A(n,\R)$.

The matrix representing $T$ is diagonal in this basis, since symmetric and antisymmetric matrices are all "eigenvectors" of $T$ (and we have a basis of them). So $M$ will have 1 as the first $\frac12n(n+1)$ elements on the diagonal, and $-1$ on the remaining $\frac12n(n-1)$ ones.

I like this method because it is already general for any order $n$ of the matrices, without doing any calculations.

Let $e_{ij}$ be the matrix with a value of $1$ at entry $(i,j)$ and zero elsewhere. This is a basis for the space $M_{n \times n}$. Then you can define your transpose operation on that space as follows:

$$T(e_{ij}) = e_{ji}$$

If you want to display this as a matrix you will need to come up with an arbitrary ordering of $\{e_{ij}\}$. Then you can use the above definition to find out which entries are $0$ or $1$.

Here is another way to think about it.

Consider a square matrix $\mathbf{A}$ of dimension $d$ for simplicity. Then consider the standard basis of $d$ column unit vectors $\mathbf{e}_i$ with elements $(\mathbf{e}_i)_j = \delta_{ij}$. These are just column vectors with a single element set to $1$ and all other elements set to zero.

A matrix $\mathbf{A}$ with elements $a_{ij}$ can always be decomposed using the basis vectors as: $$ \mathbf{A} = \sum_{ij} a_{ij}\,\mathbf{e}_i \mathbf{e}_j^T. $$ In particular, the matrix $\mathbf{A}^T$ may be written as $$ \mathbf{A}^T = \sum_{ij} a_{ji}\,\mathbf{e}_i \mathbf{e}_j^T. $$ The elements $a_{ji}$ of $\mathbf{A}^T$ can also be expressed in terms of the unit vectors: $$ a_{ji} = \mathbf{e}_j^T \mathbf{A} \mathbf{e}_i. $$ Therefore, $$ \mathbf{A}^T = \sum_{ij} \left(\mathbf{e}_j^T \mathbf{A} \mathbf{e}_i\right)\,\mathbf{e}_i \mathbf{e}_j^T = \sum_{ij} \left(\mathbf{e}_i \mathbf{e}_j^T\right) \mathbf{A} \left(\mathbf{e}_i \mathbf{e}_j^T \right). $$ If we relabel the matrices $\mathbf{e}_i \mathbf{e}_j^T$ as $\mathbf{u}_k$, with $k = 1,\dots,d^2$, then we can write $$ \mathbf{A}^T = \sum_{k} \mathbf{u}_k \mathbf{A} \mathbf{u}_k. $$ The matrices $\mathbf{u}_k$ are just all matrices containing only one non-zero element equal to $1$.

The above expression is the expression for the linear transposition map in the original matrix space. Here, we don't need to reshape the matrix in vector form. We can simply multiply the matrix by the unit matrices $\mathbf{u}_k$ on the left and on the right.

It can then be shown that if the elements of the matrix $\mathbf{A}$ are ordered by column in standard order, $\mathcal{A} = \left(a_{11},a_{21},a_{31},\dots,a_{12},a_{22},a_{32},\dots\right)^T$, the linear transposition map takes the form $$ \mathcal{A}^T = \mathcal{T}\mathcal{A}, $$ with $$ \mathcal{T} = \sum_k \mathbf{u}_k^T \otimes \mathbf{u}_k. $$ Here, $\otimes$ is the Kronecker product as defined by, e.g., Matlab's kron( ) function. For $d=2$, we have $$ \begin{align} \mathcal{T} = \left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 \end{array} \right) \end{align} $$ For $d = 3$, we have $$ \begin{align} \mathcal{T} = \left( \begin{array}{ccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{array} \right). \end{align} $$ For $d=4$, we have $$ \begin{align} \mathcal{T} = \left( \begin{array}{cccccccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right), \end{align} $$ and so on.

Notice that the transposition map is a permutation of the columns (or rows) of the identity matrix. The permutation is the permutation that groups the columns by jumps of $d$. The first four columns are columns $1,d+1,2d+1,\dots, (d-1)d+1$ of the identity matrix. The next four columns are columns $2,d+2,2d+2,\dots, (d-1)d+2$ of the identity matrix. And it goes like this in groups of $d$.

Here is the Matlab code that will give you the matrix for any dimension:

% Set the dimension of A
d = 4;
% Calculate the permutation of the columns of the identity operator
perm = (1:d^2).';
perm = reshape(perm,d,d).';
perm = perm(:).';
% Calculate the linear transposition map
T = eye(d^2);
T = T(:,perm);