Fdtxjr

How do you find a solution to a matrix $A$ that minimizes $|x|$ when $A^TA$ is not invertible? The matrix is $$A = pmatrix1 &1&2&2\1&2&3&4$$

I don't know if this helps but also in the question above this one, we are asked to find all solutions to $Ax = pmatrix0\11$

Thank you.

As others have assumed, I am assuming that this problem is linked to the previous one and that we are looking to minimize $|x|$ where $Ax=pmatrix0\11$ and $A = pmatrix1&1&2&2\1&2&3&4$. To minimize $|x|$, we can minimize $|x|^2=x^Tx$. To minimize $x^Tx$ over all $x$ so that $Ax=pmatrix0\11$, $x^T$ must be in the row space of $A$.

Suppose $AA^Tu=pmatrix0\11$. Then, it is simple to show that $|A^Tu-x|^2=|x|^2-u^Tpmatrix0\11$, and from there, it is easy to show that $x=A^Tu$ minimizes $|x|$.

If $AA^T$ is invertible, then you can find such a $u$.

Pseudoinverses:

It should be mentioned that when $AA^T$ is invertible, $A^T(AA^T)^-1$ is called the Moore-Penrose Pseudoinverse, or simply the pseudoinverse.

Mathematica:

In practice, one uses the singular value decomposition, $mathbf A=mathbf Umathbf Sigmamathbf V^top$ for solving underdetermined problems like these. Taking the SVD approach assumes that you are optimizing with respect to the Euclidean norm, $|cdot|_2$. (If you need to optimize with respect to the 1-norm or max-norm, linear programming methods are required, but I won't get into those.)

For this particular example, we have the decomposition

$$beginalign*
mathbf U&=beginpmatrix
0.4964775289157638 & -0.8680495742074279 \
0.8680495742074279 & 0.4964775289157638
endpmatrix
\
mathbf Sigma&=beginpmatrix
6.302625081925469 & 0 \
0 & 0.5262291104490325
endpmatrix
\
mathbf V&=beginpmatrix
0.2165013919416455 & -0.7061031742896186 \
0.3542296500759905 & 0.2373595096582885 \
0.5707310420176360 & -0.4687436646313301 \
0.7084593001519810 & 0.4747190193165770
endpmatrix
endalign*
$$

Computing the least-squares solution $min|mathbf Amathbf x-mathbf b|_2$ is a matter of computing $mathbf x=mathbf Vmathbf Sigma^-1mathbf U^topmathbf b$; for the particular case of $mathbf b=(0quad 11)^top$, we obtain the solution $$mathbf x=pmatrix-7\3\-4\6$$ There are other solutions, like $mathbf x=(0quad 0quad -11quad 11)^top$. All take the form $mathbf x=left(aquad bquad -11-aquad 11+fraca-b2right)^top$

I suppose that you are looking to find the value of $x$ for which $(Ax−b)^intercal(Ax−b)$ attains the minimum. As you said this problem cannot be solved as $A$ is noninvertible and I cannot see how there can be a unique solution unless we impose additional constraints on $x$.