# What is a block-matrix-transpose called and how to define it?

Consider the block matrix $\bf M$:

$$\bf M = \left[\begin{array}{cccc} \bf M_{11}&\bf M_{12}&\cdots&\bf M_{1m}\\ \bf M_{21}&\ddots&\ddots&\bf M_{2m}\\ \vdots&\ddots&\ddots&\vdots\\ \bf M_{n1}&\bf M_{n2}&\cdots&\bf M_{nm}\\ \end{array}\right]$$

I am interested in the "block-transpose" operation:

$$Tp(\bf M) = \left[\begin{array}{cccc} \bf M_{11}&\bf M_{21}&\cdots&\bf M_{n1}\\ \bf M_{12}&\ddots&\ddots&\bf M_{n2}\\ \vdots&\ddots&\ddots&\vdots\\ \bf M_{1m}&\bf M_{2m}&\cdots&\bf M_{nm}\\ \end{array}\right]$$

How can I express it? Ordinary transpose would not do, since then the individual blocks would also be transposed in the result.

I still do not know the name for such an operation, so I'm gonna keep calling it a "block transpose".

It is obvious that the operation will be a permutation - it shuffles around the elements of the matrix, right?

So if we assume a vectorization for the matrix : $\text{vec}({\bf M}) \in \mathbb R^{nm \times 1}$, the operation will be possible to represent using matrix multiplication by a permutation matrix. What remains is to find one which position for each row that should have a $1$ in it. To figure this out, we can with the row and column index matrices ($\bf r$ and $\bf c$):

$$\bf r = \left[\begin{array}{cccccc} 1&1&1&1&1&1\\2&2&2&2&2&2\\ 3&3&3&3&3&3\\4&4&4&4&4&4\\ 5&5&5&5&5&5\\6&6&6&6&6&6 \end{array}\right], \bf c = \left[\begin{array}{cccccc} 1&2&3&4&5&6\\1&2&3&4&5&6\\ 1&2&3&4&5&6\\1&2&3&4&5&6\\ 1&2&3&4&5&6\\1&2&3&4&5&6 \end{array}\right]$$

build the following helper matrix:

$${\bf h} = \left\lfloor\frac{{\bf c}+n_b-1}{n_b}\right\rfloor-\left\lfloor\frac{{\bf r}+m_b-1}{m_b}\right\rfloor$$ for example if block size is $n_b\times m_b = 2\times 2$:

$$\bf h = \left[\begin{array}{rrrrrr} 0&0&1&1&2&2\\0&0&1&1&2&2\\ -1&-1&0&0&1&1\\-1&-1&0&0&1&1\\ -2&-2&-1&-1&0&0\\-2&-2&-1&-1&0&0 \end{array}\right]$$

This matrix now counts how many steps up or down , left or right the transpose operator should push for each position in the matrix.

Now we can express a vectorized logical condition for how each element should move:

$$(\text{vec}({\bf c-h})n_b = \text{vec}({\bf c})^T)\&(\text{vec}({\bf r+h})m_b = \text{vec}({\bf r})^T)$$

For a $4\times 4$ matrix into $2\times 2$ blocks using lexical order of the vectorization:

$$\left[\begin{array}{cccccccccccccccc} 1&&&&&&&&&&&&&&&\\ &1&&&&&&&&&&&&&&\\ &&&&&&&&1&&&&&&&\\ &&&&&&&&&1&&&&&&\\ &&&&1&&&&&&&&&&&\\ &&&&&1&&&&&&&&&&\\ &&&&&&&&&&&&1&&&\\ &&&&&&&&&&&&&1&&\\ &&1&&&&&&&&&&&&&\\ &&&1&&&&&&&&&&&&\\ &&&&&&&&&&1&&&&&\\ &&&&&&&&&&&1&&&&\\ &&&&&&1&&&&&&&&&\\ &&&&&&&1&&&&&&&&\\ &&&&&&&&&&&&&&1&\\ &&&&&&&&&&&&&&&1 \end{array}\right]$$