# Existence of a symmetric matrix $A$ such that $XA=Y$.

Let $X,Y$ be vectors in $\mathbb{C}^n$, and assume that $X\ne0$. Prove that there is a symmetric matrix $B$ such that $BX=Y$.

This is an exercise from a chapter about bilinear forms. So the intended solution should be somehow related to it.

Pre-multiplying both sides by $Y^t$, we get $Y^tBX=Y^tY$. The left hand side is a bilinear form $\langle Y,X\rangle$ with $B$ as the matrix of the form with respect to the standard basis. Am I correct here?

If so, then it suffices to find a bilinear form $\langle\cdot,\cdot\rangle\colon\mathbb{C}^n\times\mathbb{C}^n\rightarrow\mathbb{C}$ such that $\langle Y,X\rangle=Y^tY$. If $Y=0$, any bilinear form will do, because $\langle0,X\rangle=0\langle 0,X\rangle =0$ by linearity in the first variable. If $Y\ne0$, it suffices to find a bilinear form such that $\langle Y,X\rangle$ is nonzero, then we can multiply by the appropriate factor. This should be very near to a complete solution, but I can't figure out the rest.

Edit: Okay, my approach seems to be completely wrong. Using Phira's hint, I think I managed to make a complete proof.

Choose an orthonormal basis $(v_1,\ldots,v_n)$ such that $v_1=\frac{X}{\|X\|}$, which can be done by Gram-Schmidt process. Let $P$ be the $n\times n$ matrix whose $i$-th column is the vector $v_i$. Then $P$ is orthogonal. Let $P^{-1}Y=(a_1,\ldots,a_n)^t$. Choose such that the first column and the first row is the vector $\frac1{\|X\|}(a_1,\ldots,a_n)$, and 0 everywhere else. Clearly $M$ is symmetric and it's easy to check that $(PMP^{-1})X=Y$. So the desired matrix is $B=PMP^{-1}$, which is symmetric because $P$ is orthogonal. $\Box$

However, this solution does not make use of bilinear forms. So there might be a simpler way.

-
One problem with your approach is that $Y^tBX=Y^tY$ (a scalar equation) does not guarantee that $BX=Y$ (a vector equation). – Marc van Leeuwen Mar 22 '12 at 8:32
I overlooked that. – gardi Mar 22 '12 at 13:43
I'd think there'd be a way to build $B$ (or $A$, as in the title) one row/column at a time. That is, you can make the first row of $B$ so its product with $X$ gives you the first entry of $Y$. That determines the first column of $B$, but can still fill out the rest of the second row of $B$ to get the second entry in $Y$ correct, etc., etc. Well, some care in the order in which you fill in the rows/columns may be needed. – Gerry Myerson Mar 23 '12 at 4:52
That is certainly feasible, but I believe there should be a smart way to use bilinear forms. – gardi Mar 23 '12 at 4:56
I like the idea you had in your second paragraph. What if you multiple by $X^t$ instead of $Y^t$? – ziggurism Mar 23 '12 at 5:28

Here is a short, constructive proof:

1. If $y = 0$, then $B = 0$.

2. If $y^Tx \ne 0$, then $B = \frac{1}{y^Tx} yy^T$.

3. If $y^Tx = 0$, then $B = \frac{\|y\|}{\|x\|} H$, where $H$ is a Householder transformation that maps $x/\|x\|$ to $y/\|y\|$ (it always exists, by this answer).

The last one can always be done (for $x \ne 0$), but I find the cases 1 and 2 more straightforward, so I decided to include them as well.

-

My solution don't use bilinear form.

Suppose that $$X=\vec{A}+\vec{B}i= \left( \begin{array}{c} a_1+b_1 i \\ a_2+b_2 i \\ \vdots \\ a_n+b_n i \\ \end{array} \right), Y=\vec{C}+\vec{D}i= \left( \begin{array}{c} c_1+d_1 i \\ c_2+d_2 i \\ \vdots \\ c_n+d_n i \\ \end{array} \right).$$ We have the following observation. If such matrix $B$ exists, suppose that $$B=S+Ti= \left( \begin{array}{cccc} s_{11}+t_{11}i & s_{12}+t_{12}i & \cdots & s_{1n}+t_{1n}i \\ s_{21}+t_{21}i & s_{22}+t_{22}i & \cdots & s_{2n}+t_{2n}i \\ \vdots & \vdots & \ddots & \vdots \\ s_{n1}+t_{n1}i & s_{n2}+t_{n2}i & \cdots & s_{nn}+t_{nn}i \\ \end{array} \right).$$ Since $BX=Y$, we have $$\sum_{j=1}^{n}(a_j+b_j i)(s_{kj}+t_{kj}i)=(c_k+d_k i).$$ Compare the real and imaginary parts, we get $$\sum_{j=1}^{n}(a_j s_{kj}-b_j t_{kj})=c_k,$$ $$\sum_{j=1}^{n}(b_j s_{kj}+a_j t_{kj})=d_k.$$ Then $$\left( \begin{array}{cccc|cccc} \vec{A}^t & 0 & 0 & 0 & -\vec{B}^t & 0 & 0 & 0 \\ 0 & \vec{A}^t & 0 & 0 & 0 & -\vec{B}^t & 0 & 0 \\ 0 & 0 & \ddots & 0 & 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & \vec{A}^t & 0 & 0 & 0 & -\vec{B}^t \\ \hline \vec{B}^t & 0 & 0 & 0 & \vec{A}^t & 0 & 0 & 0 \\ 0 & \vec{B}^t & 0 & 0 & 0 & \vec{A}^t & 0 & 0 \\ 0 & 0 & \ddots & 0 & 0 & 0 & \ddots & 0 \\ 0 & 0 & 0 & \vec{B}^t & 0 & 0 & 0 & \vec{A}^t \\ \end{array} \right) \left( \begin{array}{c} S^t e_1 \\ S^t e_2 \\ \vdots \\ S^t e_n \\ T^t e_1 \\ T^t e_2 \\ \vdots \\ T^t e_n \\ \end{array} \right)= \left( \begin{array}{c} \vec{C} \\ \vec{D} \\ \end{array} \right),$$ where $e_i$ is the $n\times 1$ column vector whose $i$ position is 1 and other 0. Write this equation by $MU=K$.

For example, when $n=2$, $$M=\left( \begin{array}{cccc|cccc} a_1 & a_2 & 0 & 0 & -b_1 & -b_2 & 0 & 0 \\ 0 & 0 & a_1 & a_2 & 0 & 0 & -b_1 & -b_2 \\ \hline b_1 & b_2 & 0 & 0 & a_1 & a_2 & 0 & 0 \\ 0 & 0 & b_1 & b_2 & 0 & 0 & a_1 & a_2 \\ \end{array} \right).$$ When $n=3$, $$M=\left( \begin{array}{ccccccccc|ccccccccc} a_1 & a_2 & a_3 & 0 & 0 & 0 & 0 & 0 & 0 & -b_1 & -b_2 & -b_3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & a_1 & a_2 & a_3 & 0 & 0 & 0 & 0 & 0 & 0 & -b_1 & -b_2 & -b_3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & a_1 & a_2 & a_3 & 0 & 0 & 0 & 0 & 0 & 0 & -b_1 & -b_2 & -b_3 \\ \hline b_1 & b_2 & b_3 & 0 & 0 & 0 & 0 & 0 & 0 & a_1 & a_2 & a_3& 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & b_1 & b_2 & b_3 & 0 & 0 & 0 & 0 & 0 & 0 & a_1 & a_2 & a_3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & b_1 & b_2 & b_3 & 0 & 0 & 0 & 0 & 0 & 0 & a_1 & a_2 & a_3 \\ \end{array} \right).$$

We claim that the set of row vectors of $M$ are linearly independent. It is sufficient to show that the $l$-th row vector $v_l$ of $M$ and $(n+l)$-th row vector $v_{n+l}$ of $M$ are linearly independent for $l=1,2,...,n$. If $\lambda v_l+\gamma v_{n+l}=\vec{0}$, where $\lambda, \gamma\in \Bbb{R}$, then $$\begin{array}{c} \lambda a_1+\gamma b_1=0 \\ \lambda a_2+\gamma b_2=0 \\ \vdots \\ \lambda a_n+\gamma b_n=0 \\ \end{array} \mbox{ and } \begin{array}{c} -\lambda b_1+\gamma a_1=0 \\ -\lambda b_2+\gamma a_2=0 \\ \vdots \\ -\lambda b_n+\gamma a_n=0 \\ \end{array}.$$ Since $X\neq 0$, there exists $i_0\in \{1,2,...,n\}$ such that $a_{i_0}\neq 0$ or $b_{i_0}\neq 0$. Then $a_{i_0}^2+b_{i_0}^2\neq 0$. Solve the equations $$\lambda a_{i_0}+\gamma b_{i_0}=0,$$ $$-\lambda b_{i_0}+\gamma a_{i_0}=0.$$ We get $\lambda(a_{i_0}^2+b_{i_0}^2)=0$ and $\lambda=0$. Similarly, we have $\gamma=0$. Hence $\lambda=\gamma=0$ and $v_{l}$ and $v_{n+l}$ are linearly independent.

Conversely, given $X\neq 0$ and $Y$, if we view the equation $MU=K$ as a linear system with $n^2$ unknowns in $U$, then since $rank(M)=2n=rank(M|K)$, by Theorem (p.174, theorem 3.11, Linear Algebra, 4 edition, Friedberg, Insel, Spence), $U$ has a solution.

Suppose that $$U=\left( \begin{array}{c} s_{11} \\ \vdots \\ s_{ij} \\ \vdots \\ s_{nn} \\ t_{11} \\ \vdots \\ t_{ij} \\ \vdots \\ t_{nn} \\ \end{array} \right).$$ For the symmetry of $B$, we need to require $s_{ij}=s_{ji}$ and $t_{ij}=s_{ji}$ in $U$. Hence we modify the vector $U$ into $U'$ such that there are $\frac{n(n+1)}{2}$ unknowns in $U'$. This modification reduces the column of $M$ into $M'$, but does not effect $rank(M)$ and $rank(M|K)$. That is, $rank(M')=rank(M)=rank(M|K)=rank(M'|K)$. Therefore, there is a solution for $U'$. Then we can construct the symmetry matrix $B$ from $U'$.

-

I propose that you choose a basis containing $X$ and think about what the equation tells you about $B$ in that basis.

You can very easily find a symmetric $B$ in that basis.

Now, you have to just think about what kind of basis change does not destroy symmetry and choose your basis accordingly.

A basis change takes $B$ to $TBT^{-1}$, if $T$ is orthogonal, this is also $TBT^{t}$ which is easily seen to be symmetric.

You can ensure that the basis change matrix is orthogonal by choosing the original basis as orthonomal. (The basis change matrix between the standard basis and an orthonormal basis is orthogonal.)

-
I don't really get it. If we take a basis containing $X$, the coordinate vector of $X$ is $(1,0,\ldots,0)$, so we can take $B$ such that the first column is identical to $Y$, the first row is also identical to $Y$, and 0 everywhere else. But I don't know what's going on when the basis changes. – gardi Mar 22 '12 at 13:42