linking two non-square matrices reshaped in row-wise and column-wise

Question

Assume I have a matrix X whose dimension is (32,8). That matrix is reshaped into X1 = (256,1) but in row-wise, it means starting the first row then second row and so on. On the other hand, if matrix X was reshaped into X2 = (256,1) too, but column-wise, it means starting first columns, then second column and so on.

My question, if we can write X1 = PX2, where P is a permutation matrix, What should be the matrix P?

NP: In case if the matrix X is square, It's clear that we can write P as below matlab code:

function p(v)
%v = vectorsize, in your case 16
for k=1:v^2
for n = 1:v^2
    p(k,n)=0;
end;
end;
for i=1:v
for j = 1:v
    k=v* (i-1) + j;
    n=v* (j-1) + i;
    p(k,n)=1;
end;
end;

The issue I'm facing now is how to deal with that when the matrix X is not square, as I mentioned, it's for example of size (32,8), how should it be?

Thank you

Answer 1

In terms of the Kronecker product, we have $$ X_1 = \sum_{i,j=1}^{m,n} x_{ij}\,e_i \otimes f_j, \quad X_2 = \sum_{i,j=1}^{m,n} x_{ji}\,f_j \otimes e_i, $$ where $e_i,f_i$ denote the $i$th column of the $m \times m$ and $n \times n$ identity matrices respectively. For your case, we have $m = 32$ and $n = 8$.

As it turns out, the permutation matrix satisfying $PX_1 = X_2$ can be written as $$ P = \sum_{i,j = 1}^{m,n} [e_j \otimes e_i][e_i \otimes f_j]^T = \sum_{i,j = 1}^{m,n} (f_je_i^T) \otimes (e_if_j^T) = \sum_{i,j = 1}^{m,n} (E_{ij})^T \otimes E_{ij} $$ where $E_{ij}$ denotes the $m \times n$ matrix with a $1$ in the $ij$ entry, and zeros everywhere else.

---

This sum formula can be directly implemented in matlab if you use the kron function.

Here's a script that uses another approach to build to build $P$; you might find this approach a bit more intuitive.

P = zeros(m*n)
col = 1;
for i = 1:m
    for j = 1:n
        E = zeros(m,n);
        E(i,j) = 1;
        P(:,col) = E(:);
        col = col + 1;
    end
end

Note that this $P$ is sometimes called a commutation matrix.

Answer 2

An alternative way is to permute the columns of identity matrix $I_{mn}$ in a rather natural manner :

m=32;n=8;
r=n*m;
I=eye(r);
J=mod(m*(0:(r-2)),r-1)+1;
P=I(:,[J,r]);

Test on random matrices :

M=rand(m,n);N=M';
max(abs(P*N(:)-M(:))), %is zero