Is matrix transpose a linear transformation? This was the question posed to me. Does there exist a matrix $A$ for which $AM$ = $M^T$ for every $M$. The answer to this is obviously no as I can vary the dimension of $M$. But now this lead me to think , if I take , lets say only $2\times2$ matrix  into consideration. Now for a matrix $M$, $A=M^TM^{-1}$ so $A$ is not fixed and depends on $M$, but the operation follows all conditions of a linear transformation and I had read that any linear transformation can be represented as a matrix. So is the last statement wrong or my argument flawed?
 A: The vector space of $n\times n$ matrices is $n^2$-dimensional, hence the matrix representation of the (indeed) linear map $X\mapsto X^T$ would have to be $n^2\times n^2$ (and you better rearrange/interprete the given $n\times n$ matrices into $n^2\times 1$ column vectors). 
A: In addition to the other answers, you certainly have a matrix representation of transpose if you treat $n\times n$ matrices as large vectors ($n^2\times 1$ vector). So that you will have to translate for example a matrix $M=[m_{ij}]_{ij}$ into $(m_{11},\dots,m_{n1},\cdots,m_{1n},\dots,m_{nn})^T$. The transpose sending $m_{ij}$ to $m_{ji}$ is simply the matrix:
$$
\begin{pmatrix}
\overbrace{1~0~\cdots~0}^{n} \\
& 1~0~\cdots~0 \\
&& \ddots\\
&&&1~0~\cdots~0 \\
0~1~\cdots~0 \\
& 0~1~\cdots~0 \\
&& \ddots\\
&&&0~1~\cdots~0 \\
\vdots&\vdots&&\vdots\\
0~\cdots~0~1 \\
& 0~\cdots~0~1 \\
&& \ddots\\
&&&0~\cdots~0~1 \\
\end{pmatrix}
$$
A: Even if we restrict $A$ and $M$ to be $n \times n$ matrices, there is no such matrix $A$.
Indeed, taking $M=I$, we get $A=I$. But then, taking a non-symmetric matrix $M$, we can't have $AM=M^T$.
A: I thought I would clarify that the transpose is a linear operation by explicitly giving the set of linear operations that need to be performed on the original matrix to get its transpose. I will give the expression for the case of a square matrix $M_{n \times n}$ but this can be extended to arbitrary matrices too.
Let $I_n$ denote the $n \times n$ identity matrix whose $i^{\rm th}$ column is the standard basis $e_i$. Let $S_{n,n}$ denote the $n^2 \times n^2$ perfect shuffle matrix corresponding to writing an $n^2 \times 1$ vector into an $n \times n$ matrix column-wise and then reading it row-wise. Then, it can be shown that
$$M^T = \sum_{i=1}^{n} \left( e_{i}^{T} \otimes I_n \right) S_{n,n} \left( I_n \otimes M \right) \left( \sum_{j=1}^{n} e_j \otimes e_j \right) e_{i}^T, $$
where $\otimes$ denotes the Kronecker product of two matrices. It should be noted that $\left( \sum_{j=1}^{n} e_j \otimes e_j \right) = vec(I_n)$ is just the vectorized form of $I_n$, $\left( I_n \otimes M \right) vec(I_n) = vec(M)$ is the vectorized form of $M$ and $S_{n,n} vec(M) = vec(M^T)$ is the vectorized form of $M^T$. Hence, this also shows that vectorization is a linear transformation.
A: The operation that transposes "all" matrices is, itself, not a linear transformation, because linear transformations are only defined on vector spaces.
Also, I do not understand what the matrix $A=M^TM^{-1}$ is supposed to be, especially since $M$ need not be invertible. Your understanding here seems to be lacking...
However:
The operation $\mathcal T_n: \mathbb R^{n\times n}\to\mathbb R^{n\times n}$, defined by
$$\mathcal T_n: A\mapsto A^T$$
is a linear transformation. However, it is an operation that maps a $n^2$ dimensional space into itself, meaning that the matrix representing it will have $n^2$ columns and $n^2$ rows!
A: While current answers clearly indicate why the reasoning is not correct, I would like to add one point that has not been mentioned so far. In trying to define $A=M^TM^{-1}$, you are making a matrix $A$ that depends on the argument $M$ that the map is being applied to. That can never be right. While describing a linear transformation as a map involves, like for any map, an expression that gives the result in terms of the argument (as here $M\mapsto M^T$), the matrix representing the linear map must by definition contain constant entries, values that do not depend on the argument (here $M$) the linear map is  potentially going to be applied to. This is similar to the coefficients of a polynomial function of$~x$: these coefficient by definition cannot involve$~x$. See also this answer to a related confused question.
Of course this takes nothing away from the other arguments, mostly that $A$ is not the right type of matrix to be considered the matrix representing the linear map $M\mapsto M^T$ (and not to mention the problem you would have for the case of non-square matrices, for which $M\mapsto M^T$ is still a linear transformation).
A: Answering the title question: "the transpose is a linear map from the space of m × n matrices to the space of all n × m matrices".
A: So if you don't want to go too abstract or crack open a functional analysis text, you could express the transpose operation as a sum.  Define $e_{i,j}$ as the $n\times n$ matrix with all entries zero except the $(i,j)$th entry, which is one.  Then we can write
$$M^T=\sum\limits_{j=1}^n \sum\limits_{i=1}^n (e_{j,i})M (e_{j,i})$$
Looking at the expression above, you can see why this can't be expressed as a single matrix to be multiplied from one direction or the other.  We need to multiply by $n^2$ matrices from both sides and sum the resulting matrix products.  Can't be done with a single $n\times n$ matrix.
To be clear, unless I've gotten it totally wrong, the $(i,j)$th  addend in this sum is an $n\times n$ matrix in which all entries are zero except the $(i,j)$th entry, which is $M_{j,i}$.
A: A linear transformation is a transformation between two vector spaces that preserves addition and scalar multiplication.  Now if $X$ and $Y$ are two $n$ by $n$ matrices then $X^T + Y^T = (X+Y)^T$ and if $a$ is a scalar then $(aX)^T$ = $a(X^T)$ so transpose is linear on the $n^2$ dimensional vector space of $n$ by $n$ matrices.
On the other hand if $A$ and $M$ are $n$ by $n$ matrices satisfying $AM = M^T$ for all $M$ then if $A$ existed and if $I$ represents the identity matrix then $A = AI = I^T = I$ but $I$ does not transpose an arbitrary matrix so $A$ does not exist unless $n$ is 1.
Note that the two situations described here refer to different vector spaces which is why the transpose can exist in the first space but not the second.  In the first case we are dealing with transformations on the $n^2$ dimensional vector space of $n$ by $n$ matrices and in the second one we are dealing with transformations on a vector space of dimension $n$.
A: Notice that the answer from Troy Woo can be written simply as $(M^\top)_{ij}=\sum_{k,l=1}^{n}\delta^k_j\delta^l_im_{kl}$. Writing $I=(e₁,\ldots,e_n)$, then $M^\top=\sum_{i,j=1}^{n}e_ie_j^\top Me_ie_j^\top$, which is another form of the answer from Kevin Bumgartner.
