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

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?

• "since I know that the matrix must be its own inverse" That's a rather curious knowledge in that situation... are you sure you know that? Mar 28, 2016 at 13:19
• @leonbloy yes - the transformation I'm trying to model with this matrix is one that must be its own inverse (for non-mathematical reasons related to the domain that the 300-dimensional space represents) and thus the matrix must be too. Mar 28, 2016 at 13:24
• The phrase "maps a set of pairs of vectors to each other" is a bit curious. How many such "sample" pairs are you given? Is it known how many in that set are reflexive (equal) pairs, or "antipodal" pairs? Mar 28, 2016 at 18:29
• @hardmath: If I'm reading things correctly, the OP has a collection of vectors $\vec{a}_i$, $\vec{b}_i$ such that $M \vec{a}_i = \vec{b}_i$ and $M \vec{b}_i = \vec{a}_i$ for all $i$. Presumably the union of these two sets is also a linearly independent set. But if that's the case, then $M(\vec{a}_i +\vec{b}_i) = \vec{a}_i + \vec{b}_i$ and $M(\vec{a}_i - \vec{b}_i) = -(\vec{a}_i - \vec{b}_i)$. These combinations of vectors ($\vec{a}_i \pm \vec{b}_i$) would span the same space as the original vectors, and there would be an equal number of reflexive and "anti-reflexive" vectors. Mar 28, 2016 at 19:46
• In fact, if the set $\{\vec{a}_i \} \cup \{\vec{b}_i \}$ is linearly independent, you would have a method to construct $M$ exactly: $M$ is a matrix which has eigenvectors $\vec{a}_i \pm \vec{b}_i$ and eigenvalues $\pm 1$. The trick comes when the set $\{\vec{a}_i \} \cup \{\vec{b}_i \}$ is linearly dependent; this is presumably the case the OP is interested in, since they are talking about finding a "best fit" instead of an exact result. Mar 28, 2016 at 19:53

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)$.

• @ joriki , you must multiply your result by a factor $2$. cf. my post.
– user91684
Mar 28, 2016 at 20:50
• @loupblanc: Thanks -- I was in the "symmetric matrices with orthogonal eigenvectors" mindset and didn't realize that we can select both eigenspaces independently -- corrected. Mar 28, 2016 at 21:44

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".

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.