6
$\begingroup$

Let $x,y$ be non-zero vectors from $\mathbb{R}^n$. Is it true, that there exists symmetric matrix $A$ such that $y = Ax$.

I was reasoning the following way. Having an equation $y = Ax$ for some symmetric matrix $A$ is equivalent to being able to solve a system of $n + \frac{n^2-n}{2}$ linear equations:

$$\begin{cases} a_{11}x_1 + ... + a_{1n}x_n = y_1 \\ \vdots \\ a_{n1}x_1 + ... + a_{nn}x_n = y_n \\ a_{12} = a_{21} \\ \vdots \\ a_{n,n-1} = a_{n-1,n} \end{cases}$$

First $n$ equations are our constraints for identity $y = Ax$ to be true and the following $\frac{n^2-n}{2}$ for symmetricity of $A$. So, in our system we have $n^2$ variables and $\frac{n^2-n}{2} + n = \frac{n^2+n}{2}$ equations. As $n^2 \geq \frac{n^2+n}{2}$ such system is always solvable. That's why such matrix $A$ always exists.

This solution was marked as wrong on exam, where did I make a mistake?

$\endgroup$
  • $\begingroup$ No, with only that, the system can be incompatible. $\endgroup$ – Rafa Budría Jun 9 '17 at 18:31
2
$\begingroup$

Note that your system is not homogeneous (since $y \neq 0$). Given a non-homogeneous system of $k$ equations in $n \geq k$ unknowns, it is not always true that this system has a solution. For example, the system

$$ 0 \cdot x + 0 \cdot y = 1 $$

clearly doesn't have a solution. In general, a system of $k$ equations in $n$ unknowns defines a linear map $B \colon \mathbb{F}^n \rightarrow \mathbb{F}^k$. If $n > k$ then this map cannot be one-to-one so you know that the homogeneous system of equations $Bx = 0$ always has a non-trivial solution $x \neq 0$. However, you can't tell automatically that $Bx = y$ has a solution because $y$ might not belong to the image of $B$.

$\endgroup$
4
$\begingroup$

It's not true that if you have more variables than equations, the system is always solvable! That's like saying a matrix with more columns than rows is always onto, which is also false.

There might be a slicker solution, but the first thing I thought of was this: Let $d = ||x||$. Then there exists a unitary matrix $U$ such that $U(x) = (d,0,0,\ldots,0)$: You can use Gram-Schmidt to create an orthonormal basis whose first vector is $x/d$, and then $U$ is the matrix whose rows are that orthonormal basis. Now, there exists a symmetric matrix A such that $A(d,0,0,\ldots,0) = U(y)$: Just set the first column of $A$ to be $U(y)/d$, and then fill in the rest of the entries to make $A$ symmetric. Now, $U^{-1}AU$ is your desired symmetric matrix sending $x$ to $y$.

$\endgroup$
  • $\begingroup$ Oops, I meant x/d $\endgroup$ – Alex Zorn Jun 9 '17 at 20:02
4
$\begingroup$

If $y^T x \ne 0$, you can take $A = (y^T x)^{-1} y y^T$.

If $y^T x = 0$, take $A = (x^T x)^{-1} (y x^T + x y^T)$.

$\endgroup$
  • 2
    $\begingroup$ Another one that works for all cases: $\frac1{x^Tx}\Bigl(yx^T + xy^T - \bigl(\frac{y^Tx}{x^Tx}\bigr)xx^T\Bigr)$ $\endgroup$ – Rahul Jun 9 '17 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.