Inverse $4\times 4$ matrix contains left upper $3\times3$ transposed matrix I am not a matrix geek or something. I just remeber a couple of things from the university math classes. Maybe the explanation is simple.
What's going on: I go through a code of a certain game and an interesting mathematical matrix property appeared when I played with some functions.
Notation: $m×n$ matrix means $m$-row $n$-column matrix.
Here we go. We have a $4\times4$ matrix $A$ that contains following elements:


*

*A 3D general rotation matrix $B$ ($3\times3$) in left upper positions of $A$
$B = \begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}$
2. A random vector $aa$ ($1×3$) in left lower positions of $A$
$aa = \begin{bmatrix}x&y&z\end{bmatrix}$
3. An additional vector $bb$ ($4×1$) in right positions of $A$
$bb = \begin{bmatrix}0\\0\\0\\1\end{bmatrix}$
It seems (by inspecting resulting numbers) that always when the matrix $A$ is invertible and we calculate its inverse $C$, then $C$ has this form:


*

*The transpose of the rotation matrix $B$ ($3\times3$) in left upper positions of $C$
$B^T = \begin{bmatrix}a&d&g\\b&e&h\\c&f&i\end{bmatrix}$
2. A vector $cc$ generally different from the vector $aa$ ($1\times3$) in left lower positions of $C$
$cc = \begin{bmatrix}t&u&v\end{bmatrix}$
3. An unchanged additional vector $bb$ ($4\times1$) in right positions of $C$
$bb = \begin{bmatrix}0\\0\\0\\1\end{bmatrix}$
So, from
\begin{bmatrix}a&b&c&0\\d&e&f&0\\g&h&i&0\\x&y&z&1\end{bmatrix}
we get the inverse
\begin{bmatrix}a&d&g&0\\b&e&h&0\\c&f&i&0\\t&u&v&1\end{bmatrix}
How can this be explained? Is there a simple proof of this or will that be hard?
Thank you for any answers!
 A: This is commonplace in computer science. The CS guys like to store a rigid motion $x\mapsto xA+b$ (here $x$ and $b$ are row vectors) in a single matrix $\pmatrix{A&0\\ b&1}$ and encode each 3D vector $x$ as a $4$-vector $\pmatrix{x&1}$, so that the rigid motion can be computed as a single matrix-vector multiplication $\pmatrix{xA+b&1}=\pmatrix{x&1}\pmatrix{A&0\\ b&1}$. And since we are talking about rigid motions, the matrix $A$ must be real orthogonal, i.e. $A^T=A^{-1}$. Geometrically, this means $A$ is composed of rotations and/or reflections.
If you want to invert the rigid motion, it is easy to verify that $\pmatrix{A&0\\ b&1}^{-1}=\pmatrix{A^{-1}&0\\ -bA^{-1}&1}$. As $A$ is orthogonal, we get $\pmatrix{A&0\\ b&1}^{-1}=\pmatrix{A^T&0\\ -bA^T&1}$ as a result.
A: OpenGL uses row-major storage order, whereas C and C++ use column-major order. The full 4-component vector and 4×4 matrix multiplication and memory ordering is actually
$$\left [ \begin{matrix}
m_0 & m_4 & m_8 & m_{12} \\
m_1 & m_5 & m_9 & m_{13} \\
m_2 & m_6 & m_{10} & m_{14} \\
m_3 & m_7 & m_{11} & m_{15}
\end{matrix} \right ] \left [ \begin{matrix}
v_0 \\ v_1 \\ v_2 \\ v_3 \end{matrix} \right ] = \left [ \begin{matrix}
m_0 v_0 + m_4 v_1 + m_8 v_2 + m_{12} v_3 \\
m_1 v_0 + m_5 v_1 + m_9 v_2 + m_{13} v_3 \\
m_2 v_0 + m_6 v_1 + m_{10} v_2 + m_{14} v_3 \\
m_3 v_0 + m_7 v_1 + m_{11} v_2 + m_{15} v_3 \end{matrix} \right ]$$
It is an unexpected quirk, and often trips programmers.
In OP's case, if we use right multiplication for matrix-vector product, then vectors are column vectors (vertical), and OP's matrices are all transposed.
user1551's answer is correct (and I arrive at the same answer here, of course), it just uses row vectors and left multiplication for the matrix-vector product. I prefer the right multiplication format, and explicitly writing out the matrices and steps, thus this answer.

The transformation matrix is defined as
$$\mathbf{M} = \left [ \begin{matrix} X_x & Y_x & Z_x & T_x \\
X_y & Y_y & Z_y & T_y \\
X_z & Y_z & Z_z & T_z \\
0 & 0 & 0 & 1 \\
\end{matrix} \right ]$$
with vectors having an implicit fourth component 1,
$$\vec{v} = \left [ \begin{matrix} v_x \\ v_y \\ v_z \\ 1 \end{matrix} \right ] $$
so that the transformed vector is
$$\mathbf{M} \vec{v}  = \left [ \begin{matrix} X_x & Y_x & Z_x & T_x \\
X_y & Y_y & Z_y & T_y \\
X_z & Y_z & Z_z & T_z \\
0 & 0 & 0 & 1 \\
\end{matrix} \right ] \left [ \begin{matrix} v_x \\ v_y \\ v_z \\ 1 \end{matrix} \right ]
 = \left [ \begin{matrix}
X_x v_x + Y_x v_y + Z_x v_z + T_x \\
X_y v_x + Y_y v_y + Z_y v_z + T_y \\
X_z v_x + Y_z v_y + Z_z v_z + T_z \\
1 \end{matrix} \right ]$$
The three first components of the result are the same as rotation by the upper left 3×3 matrix of $\mathbf{M}$, plus translation after rotation,
$$\mathbf{R}\vec{p} + \vec{T} = \left [ \begin{matrix}
X_x & Y_x & Z_x \\
X_y & Y_y & Z_y \\
X_z & Y_z & Z_z \\
\end{matrix} \right ] \left [ \begin{matrix}
p_x \\ p_y \\ p_z \end{matrix} \right ] + \left [ \begin{matrix}
T_x \\ T_y \\ T_z \end{matrix} \right ] = \left [ \begin{matrix}
X_x p_x + Y_x p_y + Z_x p_z + T_x \\
X_y p_x + Y_y p_y + Z_y p_z + T_y \\
X_z p_x + Y_z p_y + Z_z p_z + T_z \\
\end{matrix} \right ]$$
The inverse operation is
$$\mathbf{R}^{-1}\left(\vec{p} - \vec{T}\right) = \mathbf{R}^{-1}\vec{p} - \mathbf{R}^{-1}\vec{T}$$
Pure rotation matrices are orthogonal, which means their inverse is their transpose. If $\mathbf{R}$ is a rotation matrix, then $\mathbf{R}^{-1} = \mathbf{R}^T$. Then,
$$\mathbf{R}^{-1}\left(\vec{p} - \vec{T}\right) = \mathbf{R}^T\vec{p} - \mathbf{R}^T\vec{T} = \left [ \begin{matrix}
X_x p_x + X_y p_y + Z_x p_z - X_x T_x - X_y T_y - X_z T_z \\
Y_x p_x + Y_y p_y + Z_y p_z - Y_x T_x - Y_y T_y - Y_z T_z \\
Z_x p_x + Z_y p_y + Z_z p_z - Z_x T_x - Z_y T_y - Z_z T_z \\
\end{matrix} \right ]$$
If we use
$$\vec{t} = \left [ \begin{matrix} t_x \\ t_y \\ t_z \end{matrix} \right ]
 = -\mathbf{R}^T\vec{T} = - \left [ \begin{matrix}
X_x & X_y & X_z \\
Y_x & Y_y & Y_z \\
Z_x & Z_y & Z_z \\
\end{matrix} \right ] \left [ \begin{matrix}
T_x \\ T_y \\ T_z \end{matrix} \right ] = \left [ \begin{matrix}
- X_x T_x - X_y T_y - X_z T_z \\
- Y_x T_x - Y_y T_y - Y_z T_z \\
- Z_x T_x - Z_y T_y - Z_z T_z \\
\end{matrix} \right ]$$
then we can write
$$\mathbf{M}^{-1}\vec{v} = \left [ \begin{matrix}
X_x & X_y & X_z & t_x \\
Y_x & Y_y & Y_z & t_y \\
Z_x & Z_y & Z_z & t_z \\
0 & 0 & 0 & 1 \\
\end{matrix} \right ] \left [ \begin{matrix}
v_x \\ v_y \\ v_z \\ 1 \end{matrix} \right ] = \left [ \begin{matrix}
X_x v_x + X_y v_y + X_z v_z - X_x T_x - X_y T_y - X_z T_z \\
Y_x v_x + Y_y v_y + Y_z v_z - Y_x T_x - Y_y T_y - Y_z T_z \\
Z_x v_x + Z_y v_y + Z_z v_z - Z_x T_x - Z_y T_y - Z_z T_z \\
\end{matrix} \right ]$$
As OP observed, the inverse transformation has the upper left 3×3 submatrix transposed, and the translation part changed.
