Solving the matrix equation $X^tA+A^tX=0$ for $X$ in terms of $A$

Suppose that I know $$A$$. And all matrices in the equation are square matrices. I want to solve for $$X$$ given that

$$X^tA + A^tX = 0$$

I'm not really good at matrix calculus. Is it possible to solve this problem in the sense that we find a closed form solution for $$X$$ in terms of $$A$$ and possibly some other vector B (as a free parameter, if necessary)? For example, when $$A = I$$, we see that $$X=B$$ for any anti-symmetric matrix $$B$$.

The motivation for this question comes from computer vision. We know that a homography $$H$$ between two photos is induced by a plane in space if and only if $$H^tF$$ is anti-symmetric where $$F$$ is the fundamental matrix. I also know that $$F$$ can be parametrized as $$F=[e]_{\times}M$$ where $$M$$ is invertible. Now I want to find a general form for $$H$$. Hence, this question.

Edit: Since the general case might be too broad and challenging, let's narrow down our attention to the simpler case where $$A$$ and $$X$$ are $$3 \times 3$$ matrices and $$A$$ is not invertible. The general case seems very interesting too.

Edit: you might look into methods for solving Sylvester Equations which are of the form $$AX+XB=C$$.

General Case

I doubt this is the best way to solve the equation, but it is at least one way to solve it.

Write, $$X = \begin{bmatrix} | & | & & | \\ x_1 & x_2 & & x_n \\ | & | & & | \\ \end{bmatrix} , ~~ A = \begin{bmatrix} | & | & & | \\ a_1 & a_2 & & a_n \\ | & | & & | \\ \end{bmatrix}$$

Then the $$i,j$$ entry of $$X^TA+A^TX = 0$$ gives, $$x_i^Ta_j + a_i^Tx_j = a_j^Tx_i + a_i^Tx_j = 0$$

We can rewrite this as a matrix vector equation $$\tilde{A}x = 0$$ $$\begin{bmatrix} a_1^T & & & & \\ a_2^T & a_1^T & & & \\ a_3^T & & a_1^T & & \\ \vdots & & &\ddots & \\ a_n^T & & & & a_1^T \\ \hline a_2^T & a_1^T & & \cdots & \\ & a_2^T \\ & a_3^T & a_2^T & & \\ & \vdots & & \ddots \\ & a_n^T & & & a_2^T \\\hline &&\vdots \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = 0$$ where the matrix $$\tilde{A}$$ is size $$n^2\times n^2$$ and the vector $$x$$ is size $$n^2\times 1$$.

Note that a lot of the rows are identical. In particular, there are at most $$n(n-1)/2$$ unique rows. This tells us that the null space of $$\tilde{A}$$ is at least dimension $$n^2-n(n-1)/2 = n(n+1)/2$$. Each element of the null space of $$\tilde{A}$$ gives a solution to the original equation, so there are at least this many solutions.

So finding solutions to the original equation amounts to finding vectors in the null space of this new matrix (there are many existing libraries to do this).

3 by 3 case

I used mathematica and the above method to find all solutions $$X$$. We define entries of $$A$$ by $$A = \begin{bmatrix} A1 & B1 & C1 \\ A2 & B2 & C2 \\ A3 & B3 & C3 \\ \end{bmatrix}$$

We input this to mathematica, compute the null space of $$\tilde{A}$$ as defined above, and then reshape vectors from the null space.

AA = {{A1, A2, A3}}\[Transpose];
BB = {{B1, B2, B3}}\[Transpose];
CC = {{C1, C2, C3}}\[Transpose];

A = ArrayFlatten[{{AA\[Transpose], 0, 0}, {BB\[Transpose],
AA\[Transpose], 0}, {CC\[Transpose], 0,
AA\[Transpose]}, {BB\[Transpose], AA\[Transpose], 0}, {0,
BB\[Transpose], 0}, {0, BB\[Transpose],
CC\[Transpose]}, {CC\[Transpose], 0, AA\[Transpose]}, {0,
CC\[Transpose], BB\[Transpose]}, {0, 0, CC\[Transpose]}}];

NA = NullSpace[A]


Then the solutions are linear combinations of the following: $$X1= \left( \begin{array}{ccc} -\frac{\text{A3} \text{B2} \text{C1}-\text{A2} \text{B1} \text{C3}}{\text{C1} (\text{B2} \text{C1}-\text{B1} \text{C2})} & -\frac{\text{B2} (\text{B3} \text{C1}-\text{B1} \text{C3})}{\text{C1} (\text{B2} \text{C1}-\text{B1} \text{C2})} & -\frac{\text{C3}}{\text{C1}} \\ -\frac{\text{A1} \text{B1} \text{C3}-\text{A3} \text{B1} \text{C1}}{\text{C1} (\text{B2} \text{C1}-\text{B1} \text{C2})} & \frac{\text{B1} \text{B3} \text{C1}-\text{B1}^2 \text{C3}}{\text{C1} (\text{B2} \text{C1}-\text{B1} \text{C2})} & 0 \\ -\frac{\text{A1} \text{B2}-\text{A2} \text{B1}}{\text{B1} \text{C2}-\text{B2} \text{C1}} & 0 & 1 \\ \end{array} \right)$$

$$X2= \left( \begin{array}{ccc} -\frac{\text{A2}}{\text{C1}} & -\frac{\text{B2}}{\text{C1}} & -\frac{\text{C2}}{\text{C1}} \\ \frac{\text{A1}}{\text{C1}} & \frac{\text{B1}}{\text{C1}} & 1 \\ 0 & 0 & 0 \\ \end{array} \right)$$

$$X3= \left( \begin{array}{ccc} -\frac{\text{A3} \text{C2}-\text{A2} \text{C3}}{\text{B1} \text{C2}-\text{B2} \text{C1}} & -\frac{\text{B3} \text{C2}-\text{B2} \text{C3}}{\text{B1} \text{C2}-\text{B2} \text{C1}} & 0 \\ -\frac{\text{A1} \text{C3}-\text{A3} \text{C1}}{\text{B1} \text{C2}-\text{B2} \text{C1}} & -\frac{\text{B3} \text{C1}-\text{B1} \text{C3}}{\text{B2} \text{C1}-\text{B1} \text{C2}} & 0 \\ -\frac{\text{A2} \text{C1}-\text{A1} \text{C2}}{\text{B1} \text{C2}-\text{B2} \text{C1}} & 1 & 0 \\ \end{array} \right)$$

• This is an interesting answer. I need some more time to digest your calculations. One thing I learned from this is that mathematica can do algebraic manipulations with symbols. That's great. At one point you say that there are at least $n(n+1)/2$. What do you mean by that? Shouldn't there be infinitely many solutions always? Dec 27, 2018 at 21:33
• Mathematica is great for symbolic manipulations! You're right that there are infinitely many solutions. I should have said linearly independent solutions.
– tch
Dec 27, 2018 at 21:37

The problem reduces to solve the system $$A^TX=K$$ when $$K$$ is skew-symm. Let $$rank(A)=r$$; we assume that $$A$$ is real..

The condition for the existence of a solution is

$$(*)$$ $$A^T{A^T}^+K=K$$

where $$Z^+$$ is the Moore-Penrose inverse of $$Z$$, cf.

https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse#Obtaining_all_solutions_of_a_linear_system

If $$(*)$$ is satisfied, then the general solution is

$$(**)$$ $$X={A^T}^+K+(I_n-{A^T}^+A^T)W$$, where $$W\in M_n$$ is arbitrary.

$$\textbf{Step 1.}$$ Solving $$(*)$$. Using the SVD of $$A$$, one has $$A^T{A^T}^+=V^* diag(I_r,0_{n-r})V$$, where $$V$$ is unitary and $$K=V^*diag(L_r,0_{n-r})$$ where $$L\in M_r$$ is skew arbitrary. Thus, the admissible $$K$$ go through a vector space of dimension $$r(r-1)/2$$.

$$\textbf{Step 2.}$$ Write $$(**)$$ (using the $$K$$ obtained in step 1); note that $$I_n-{A^T}^+A^T=U^* diag(0_r,I_{n-r})U$$ where $$U$$ is unitary. Then the block $$(I_n-{A^T}^+A^T)W$$ (when $$W$$ varies in $$M_n$$) spans a vector space of dimension $$n(n-r)$$. Finally, the vector space of solutions $$X$$ has dimension $$r(r-1)/2+(n-r)n$$.