# Permute any two entries in a $n\times n$ matrix.

Let $A$ be an $8 \times 8$ matrix with integer coefficients. I want to permute two entries in $A$, any two entries as needed: In general, for any two entries $a_j,b_k$ in the matrix is it possible to do this with some matrix $B$ dependent on $a_j,b_k$?

I know about permutation matrices, but they only permute entire rows and columns not individual entries.

Edit 1:

For example: Say I want to permute $x_{12}$ with $x_{33}$, I want a matrix $B$ suh that :

$$\begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1n} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2n} \\ x_{31} & x_{32} & x_{33} & \dots & x_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{n1} & x_{n2} & x_{n3} & \dots & x_{nn} \end{bmatrix}B= \begin{bmatrix} x_{11} & x_{33} & x_{13} & \dots & x_{1n} \\ x_{21} & x_{22} & x_{23} & \dots & x_{2n} \\ x_{31} & x_{32} & x_{12} & \dots & x_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{n1} & x_{n2} & x_{n3} & \dots & x_{nn} \end{bmatrix}$$

Thanks.

P.s[Moderators]: Edit tags as appropriate, I added as many as made sense to me.

• What do you mean by permuting two entries? What do you mean is it possible to do this with some matrix $B$? Commented Dec 26, 2017 at 21:21
• I will edit. One sec. Commented Dec 26, 2017 at 21:27
• Here $A$ is said to be an $8\times 8$ integer matrix. The totality of such matrices spans a vector space over $\mathbb{Q}$ of dimension $64$, and there is a linear transformation that swaps the $i,j$-entry with (say) the $k,m$-entry. However this is a linear transformation on the $64$-dimensional space, so it is not represented by any matrix $B$ that is $8\times 8$ like the matrices $A$. Commented Dec 26, 2017 at 21:31
• The dimension of B is not a restriction...it could be as big as it needs to be, so long as I know how to create them. Commented Dec 26, 2017 at 21:34
• What do you mean by "almost always" in this case? That statement is false for most meanings of the term. Commented Dec 27, 2017 at 6:25

I doubt you can do it with "a matrix" $B$.

Here's an ugly algorithm using matrix arithmetic. You can multiply on the left and on the right by matrices with one $1$ and all the rest $0$ to build a matrix with one entry untouched and all the other entries $0$. Do this for all $64$ entries in the original matrix, permute rows and columns for the pair of entries you want to swap, and add everything back up.

I doubt this is what you're after.

• You're correct in saying there is no single matrix which can generate an arbitrary permutation. This is because left and right multiplication can only permute the rows and columns respectively. I find this easiest to see when considering permutations on rectangular matrices where you cannot even ensure the left and right matrices are the same size. Commented Dec 26, 2017 at 21:52
• Nope, not at all. Computationally inefficient, strongly so. @Cyclo, any suggestions? Commented Dec 27, 2017 at 5:52

The dimension of $B$ is not a restriction...it could be as big as it needs to be, so long as I know how to create them.

Consider a "flatten" operator $\iota$ that maps $A$ to a single row of length $n^2$ by concatenating successive rows of $A$. Then let $B$ be the $n^2\times n^2$ permutation matrix that swaps entries $(i-1)n+j$ and $(k-1)n+m$ for any fixed $i,j,k,m \in \{1,\ldots,n\}$.

Then $\iota(A)B = \iota(\tilde{A})$ where $\tilde{A}$ is the result of swapping the $i,j$ and $k,m$ entries of $A$.

So if you allow for "flattening" of $A$ and unflattening the result of multiplying the long row by $B$ to $\tilde{A}$, then we can swap two specific entries of matrix $A$ through multiplication by (much larger) matrix $B$. Some programming languages (such as Matlab/Octave/MLab) support this through a "reshape" function.

• This is useful.Thank you. Commented Dec 29, 2017 at 1:27

Of course there is no such $B$ (EDIT: assuming you want a fixed $B$ that works for every $A$). The $j$'th row of $AB$ is (the $j$'th row of $A$) $B$. It doesn't depend on any other row. You can do any linear transformation of that row (but you will be doing the same linear transformation to each of the other rows).

• I figured as much, but was curious to see if there is any method that resembles such a B. Approximate or otherwise. Commented Dec 27, 2017 at 5:51
• I want a $B$ for a given pair of positions in the matrix $A$. Commented Dec 29, 2017 at 1:23