Minimum number of real variables required to describe all n by n matrices that are their own inverse

Question

This is related to Is the identity matrix the only matrix which is its own inverse?, but that question does not contain an answer to this one.

I am attempting to find - probably by using a learning algorithm - the linear transformation in $\mathbb{R}^{300}$ that most closely maps a set of pairs of vectors to each other. Naively, this would require me to perform gradient descent (or some other learning algorithm) on $300\cdot 300 = 90000$ variables - one variable for each cell in my matrix. However, since I know that the matrix must be its own inverse, I suspect I can use a smaller number of variables.

Is this the case? Is there some function of fewer than 90000 reals whose range is (or at least contains) all 300 by 300 matrices who are their own inverse? If so, what is that function, and what is the minimum number of reals required in its input?

Answer 1

As shown at Is the matrix $A$ diagonalizable if $A^2=I$, an involutory matrix is diagonalizable. Then clearly its eigenvalues must be all be $\pm1$, and conversely every diagonalizable matrix with eigenvalues $\pm1$ is involutory. Thus the involutory matrices are fully characterized as the diagonalizable matrices with all eigenvalues $\pm1$. For an $n\times n$ matrix, you can select $k$ eigenvalues to be $+1$; then you can select any of the $k$-dimensional subspaces, which form a manifold of dimension $k(n-k)$, as the eigenspace for $+1$ and any of the $(n-k)$-dimensional subspaces, which form a manifold of dimension $(n-k)(n-(n-k))=k(n-k)$, as the eigenspace for $-1$ (in the generic case the intersection will be trivial), so the dimension of the manifold of involutary matrices with $k$ eigenvalues $+1$ is $2k(n-k)$.

Answer 2

As the Question asks about "attempting to find... the linear transformation in $\mathbb{R}^{300}$ that most closely maps a set of pairs of vectors to each other," let me propose a computational approach based on @joriki's analysis of possible solutions to $A^2 = I$.

Suppose that we have a finite set of vectors and their images $(u_i,Au_i)$. If there were enough vectors $u_i$ to span $\mathbb{R}^{300}$, these pairs would exactly determine the matrix $A$.

Since the matrix we want must satisfy $A^2 = I$, its construction depends on a choice of subspaces $U_0,U_1$ such that $U_0 \oplus U_1 = \mathbb{R}^{300}$, where $U_0$ is the eigenspace of $A$ corresponding to $\lambda = -1$ and $U_1$ is the eigenspace corresponding to $\lambda = 1$.

In exact arithmetic $(I-A)/2$ would be a projection onto $U_0$ and $(I+A)/2$ a projection onto $U_1$. It may be possible to precisely recover a spanning set $v_i = (u_i - Au_i)/2$ for $U_0$ and a spanning set $w_i = (u_i + Au_i)/2$ for $U_1$ even if the $u_i$ do not fully span $\mathbb{R}^{300}$.

Since $U_0 \cap U_1 = \{0\}$ by design, our goal is to extract the "best" basis for $U_0$ from vectors $v_i$ and basis for $U_1$ from vectors $w_i$ subject to having a combined dimension $300$ and linear independence.

A naive approach would be to perform row reduction on matrix $V$ consisting of rows $v_i$ and on matrix $W$ consisting of rows $w_i$. In the presence of rounding errors caused by floating point arithmetic, a more accurate determination of rank for $V,W$ can be achieved by orthogonal transformations rather than elementary row operations. See QR factorization and consider the results applied to $V,W$ to obtain the best combination of bases with dimension $300$.

Studies in the literature of the best rank-finding orthogonal algorithms often include the phrase "rank-revealing QR".

Answer 3

Proposition. i) $V=\{A\in M_n(\mathbb{R})|A^2=I_n\}$ is an algebraic set of dimension $2f(n-f)$ where $f=int(n/2)$ and ii) $V_k=\{A\in M_n(\mathbb{R})|A^2=I_n,dim(\ker(A-I))=k\}$ is an algebraic set of dimension $2k(n-k)$.

Proof of ii). $A\in V_k$ is defined by $E_k=\ker(A-I)$ and $F_{n-k}=\ker(A+I)$. $E_k$ is in the Grassmannian $G_k$ of dimension $k(n-k)$ and $F_{n-k}$ is in the Grassmannian $G_{n-k}$ of dimension $k(n-k)$. Two generic such subspaces have intersection $\{0\}$. Then the dimension of $V_k$ is $2k(n-k)$.

Proof of i). The dimension of an algebraic set is the maximum of the dimensions of its components.

Conclusion. If you want to parametrize $V$, then you must use $\approx \dfrac{n^2}{2}$ real parameters.

NB. If you consider only the orthogonal symmetries , then $F$ is fixed by the choice of $E$ and the required dimension is the half of the previous one.