Can elementary row operations be done by both left and right multiplication? So I know that interchanging two rows of a matrix $A$ can be done by left-multiplying it by some permutation matrix $P$ to get $PA$. Similarly, interchanging two columns can be done by right-multiplication, $AP$. 
My question is: Can you interchange rows by right-multiplication (of some matrix, not necessarily a permutation matrix)? And interchange columns by left-multiplication? In general, can every elementary row (or column) operation be represented as both a left- and right-multiplication?
Edit: if $A$ is invertible, and we want to find a matrix $B$ such that $AB = PA$, then we can solve for $B$ by multiplying both sides by $A^{-1}$ to get $B = A^{-1}PA$. So this is how we can interchange two rows by right-multiplication. Similarly for interchanging columns. But what if $A$ isn't invertible? Can we characterize the cases when it is or isn't possible?
 A: Interesting question! There is a nice relation between your question and the area of mathematics called representation theory which I want to highlight. The short answer is:


*

*The only matrices $A$ for which all elementary columns operations on $A$ can be performed by left multiplication $PA$ are the full rank matrices and the zero matrix.

*When $\operatorname{char} \mathbb{F} = 0$, the only matrices $A \in M_{m \times n}(\mathbb{F})$ for which all permutation column operations can be performed by left multiplication $PA$ are the matrices $A$ for which $\ker(A) = \textrm{Span} \{ e_1 + \dots + e_n \}$ (this implies that the sum of elements in any row is zero) or $\ker(A) = \{ (x_1,\dots,x_n)^T \, | \, x_1 + \dots + x_n = 0 \}$ (this implies that all the columns of $A$ are identical) in addition to the previous ones.


For a "non-obvious at first look" example of $(2)$, the matrix
$$ A = \begin{pmatrix} 1 & 2 & -3 \\ 0 & 1 & -1 \\ 1 & 1 & -2 \end{pmatrix} $$
has rank two but any column permutation operation on $A$ can be realized as left multiplication $PA$ (not necessarily by a permutation matrix $P$!).

For simplicity of notation, I'll go the other way and discuss which column operations can be implemented using left multiplication.
Let's start with the following question. We have a matrix $Q \in M_n(\mathbb{F})$ which might be a permutation matrix, a "add a multiple of a column to another column" or an arbitrary matrix. The first question you can ask is: 
What are the matrices $A \in M_{m \times n}(\mathbb{F})$ for which there exists $P \in M_m(\mathbb{F})$ such that $PA = AQ$. So for example, if $Q$ describes swapping two specific columns, you ask what are the matrices $A$ for which the swapping can be done by left multiplication. If $PA = AQ$ and $x \in \mathbb{F}^n$ such that $Ax = 0$ then we have
$$ 0 = P(Ax) = (PA)x = (AQ)x = A(Qx). $$
This shows that $Q(\ker(A)) \subseteq \ker(A)$ so that $\ker(A)$ must be $Q$-invariant. 
In fact, this is also a sufficient condition. Let's assume $\ker(A)$ is $Q$-invariant and write the columns of $A$ as $a_1,\dots,a_n$. They might be linearly dependent so choose a basis for the column space $a_{i_1},\dots,a_{i_k}$, define $Pa_{i_j} = AQe_j$ and extend $P$ arbitrary outside the image of $A$. Then by definition $(PA)e_{i_j} = Pa_{i_j} = AQe_{i_j}$. What about all other standard vectors? Let's say that $1 < i_1$ and so $a_1$ depends linearly on $a_{i_1},\dots,a_{i_k}$. Write $a_1 = x_1 a_{i_1} + \dots + x_k a_{i_k}$. Then
$$ (PA)e_1 = Pa_1 = P(x_1 a_{i_1} + \dots + x_k a_{i_k}) = x_1 Pa_{i_1} + \dots + x_k P a_{i_k} \\
= x_1 AQe_{i_1} + \dots + x_k AQe_{i_k}. $$
However, $x_1 e_{i_1} + \dots + x_k e_{i_k} - e_1 \in \ker(A)$ so that by assumption
$$ A(Q(x_1 e_{i_1} + \dots + x_k e_{i_k} - e_1)) = x_1 AQe_{i_1} + \dots + x_k AQe_{i_k} - AQe_1 = 0 $$
so 
$$ (PA)e_1 = x_1 AQe_{i_1} + \dots + x_k AQe_{i_k} = AQe_1. $$
This gives us a concrete answer: Given $Q \in M_n(\mathbb{F})$, the matrices $A \in M_{m \times n}(\mathbb{F})$ for which there exists $P \in M_m(\mathbb{F})$ such that $PA = AQ$ are precisely the matrices for which $\ker(A)$ is $Q$-invariant. In particular, if $m = n$ and $A$ is invertible, this can always be done as you noticed.
Example: Let's say
$$ Q = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \in M_3(\mathbb{R}) $$
so that $AQ$ swaps the first two columns of $A$. The $Q$-invariant subapsces of $A$ are:


*

*$V_0 = \{ 0 \}$.

*$V_1 = \textrm{Span} \{ e_1, e_2 \}$

*$V_2 = \textrm{Span}\{ e_3 \}$.

*$V_3 = \textrm{Span}\{ e_1, e_2, e_3 \}$.


The $3 \times 3$ matrices we obtain are:


*

*Invertible matrices $A \in M_{3 \times 3}(\mathbb{R})$.

*Matrices $A \in M_{3 \times 3}(\mathbb{R})$ whose kernel is precisely $\textrm{Span} \{ e_1, e_2 \}$:
$$ \begin{pmatrix} 0 & 0 & a \\ 0 & 0 & b \\ 0 & 0 & c \end{pmatrix}, \, c \neq 0 $$

*Matrices $A \in M_{3 \times 3}(\mathbb{R})$ whose kernel is precisely $\textrm{Span} \{ e_3 \}$:
$$ \begin{pmatrix} a & b & 0 \\
c & d & 0 \\
e & f & 0 \end{pmatrix}, \, ad - bc \neq 0 \textrm{ or } cf - de \neq 0. $$
Note that for such matrices, you can't always get $AQ$ as $PA$ when $P$ is a permutation matrix but you can always find $P$ such that $PA = AQ$.

*The zero matrix.


In general, the invariant subspaces depend over which field you are working on. If you would have considered $Q$ above as a complex matrix, you would get more invariant subspaces (because $Q$ is diagonalizable over $\mathbb{C}$) and more matrices $A$.

Now, that we "answered" the question for one $Q$, let's ask what are the matrices $A$ for which all column permutations can be realized as left multiplication? This means we are looking for matrices $A$ such that for all $Q_{\sigma}$, the subspace $\ker(A)$ is $Q_{\sigma}$-invariant where $\sigma \in S_n$ is a permutation. In the language of representation theory, the group $S_n$ acts on $\mathbb{F}^n$ via $Q_{\sigma}$ and we are looking for matrices $A$ for which $\ker(A)$ is a sub-representation of $\mathbb{F}^n$. It is well known that in characteristic zero, there are only two non-trivial sub-representations given by
$$ \{ (x_1, \dots, x_n)^T \, | \, x_1 + \dots + x_n = 0 \}, \, \operatorname{Span} \{ (1, \dots, 1) \}. $$
This gives us the result quoted in the beginning of the answer.
Finally, we can ask what are the matrices for $A$ which all elementary column operations can be realized by left multiplication. Since the elementary operations generate the group $GL_n(\mathbb{F})$, the question again translates to finding the subrepresentations of $GL_n(\mathbb{F})$ on $\mathbb{F}^n$. In this case, there are no non-trivial subrepresentations so the only matrices for which this is possible are the zero matrix and the matrices with full rank.
A: If $A$ isn't invertible, it's not always possible.

For a simple counterexample, let
$$
A
=
\pmatrix{
1&0\\
0&0\\
}
$$
Then for any matrix
$$
B
=
\pmatrix{
w&x\\
y&z\\
}
$$
we get
$$
AB
=
\pmatrix{
w&x\\
0&0\\
}
$$
which can't swap the rows of $A$.

So that answers the original question.

But there are some singular matrices $A$ for which row swaps via right multiplication are possible.

For example, if $n > 1$ and $A$ is an $n{\,\times\,}n$ matrix with all rows are equal, then for any $n{\,\times\,}n$ permutation matrix $P$, we have $PA=A$, hence using $B=I_n$, we get $PA=AB$.

For another example, if
$$
A=
\pmatrix{
1&-1\\
-1&1\\
}
$$
and
$$
B=
\pmatrix{
-1&0\\
0&-1\\
}
$$
then $AB=-A$ which is the same as $A$ with rows swapped.

As a partial converse, we have the following claim . . .

Claim:

If $K$ is a field and $A\in M_n(K)$ is such that 


*

*Some column of $A$ is non-constant and has nonzero sum.$\\[4pt]$

*For all $n{\,\times\,}n$ permutation matrices $P$, there exists $B\in M_n(K)$ such that $PA=AB$.


then $A$ must be non-singular.

Proof:

Assume the hypothesis.

Then for some $j\in\{1,...,n\}$, the $j$-th column-vector $v_j$ of $A$ is non-constant and has nonzero sum.

It follows (see the lemma, proved at the end) that the span of the set of permutations of $v_j$ is all of $K^n$.

Thus, letting $e_j\in K^n$ be the $j$-th standard basis vector, there exist $n{\,\times\,}n$ permutation matrices $P_1,...,P_n$ such that the vectors $P_1Ae_j,...,P_nAe_j$ are linearly independent.

By hypothesis, there exist $B_1,...,B_n\in M_n(K)$ such that for all $i\in\{1,...,n\}$, we have $P_iA=AB_i$.

Then the equations
\begin{align*}
P_1Ae_j&=AB_1e_j\\[4pt]
&\;\,\vdots\\[4pt]
P_nAe_j&=AB_ne_j\\[4pt]
\end{align*}
must all hold, hence, since the vectors on the left are linearly independent, while the vectors on the right are in the image of $A$, it follows that the image of $A$ is all of $K^n$, so $A$ is non-singular, as was to be shown.

To tie up loose ends, we prove the following lemma . . .

Lemma:

Fix a positive integer $n > 1$, and let $X=K^n$ where $K$ is a field.

Let ${\large{\mathcal{P}}}$ be the set of $n{\,\times\,}n$ permutation matrices.

If $x\in X$ is non-constant and has nonzero sum, then the span of the set $\{Px{\,\mid\,}P\in {\large{\mathcal{P}}}\}$ is all of $X$.

Proof:

Suppose $x\in X$ is non-constant and has nonzero sum.

Let $V$ be the span of the set $\{Px{\,\mid\,}P\in {\large{\mathcal{P}}}\}$.

Suppose $V$ is a proper subspace of $X$.

Then there exists some nonzero vector $g\in X$ such that $g{\,\cdot\,}v=0$, for all $v\in V$.

In particular, we have $g{\,\cdot\,}Px=0$, for all $P\in {\large{\mathcal{P}}}$.

Then $g{\,\cdot\,}x=g{\,\cdot\,}I_nx=0$, hence, since $g$ is nonzero and $x$ has nonzero sum, it follows that $g$ is non-constant.

Thus, suppose $g=(g_1,...,g_n)$ with $g_i\ne g_j$.

Since $x$ is non-constant, there exists $y\in\{Px{\,\mid\,}P\in \mathcal{P}\}$ such that $y_i\ne y_j$

Let $T\in {\large{\mathcal{P}}}$ be the transposition that swaps the entries in positions $i,j$ but leaves all other entries fixed.
\begin{align*}
\text{Then}\;\;&g{\,\cdot\,}y=0\;\,\text{and}\;\,g{\,\cdot\,}Ty=0\\[4pt]
\implies\;&g{\,\cdot\,}y-g{\,\cdot\,}Ty=0\\[4pt]
\implies\;&(g_iy_i+g_jy_j)-(g_iy_j+g_jy_i)=0\\[4pt]
\implies\;&(g_i-g_j)(y_i-y_j)=0\\[4pt]
\end{align*}
contradiction, since $g_i\ne g_j$ and $y_i\ne y_j$.

Hence we must have $V=X$, which completes the proof of the lemma.
A: If you allow right multiplication with transposes then we have:
$$(A^TP^T)^T=PA$$
but as @quasi shows, it's otherwise impossible.
A: Here is a partial answer (an observation of a few simple facts).
Claim: If $A$ has a zero row, then $AB$ always has a zero row.
Proof: This follows from the definition of matrix multiplication ($i$th row of $AB$ $=$ $i$th row of $A$ times $B$). $\square$
In particular, if $A$ has a zero and nonzero row, then those two rows can’t be swapped by right multiplication.
Claim: If $AB = PA$ for some invertible $B$ and some permutation matrix $P$, then $AB = AB^{-1}$.
Proof: $AB = PA \implies P(AB)B^{-1} = P(PA)B^{-1} \implies PA = AB^{-1}$. $\square$
In particular, if $A$ is invertible, then $B = B^{-1}$.
Claim If $AB = PA$ for some permutation matrix $P$, then $\text{rank}(A) = \text{rank}(AB)$.
Proof: $\text{rank}(A) = \text{rank}(PA) = \text{rank}(AB)$. $\square$
