Efficiently solve $n \times n$ linear system

Question

You already have the LU factorization with partial pivoting of $A \in R^{n \times n}$ (i.e. $PA=LU$). Explain how to efficiently solve the $ n \times n $ linear system $$A^T Ax=b$$ without computing another PLU factorization.

Where do I even start??

Answer 1

Solve $A^T y = b$ first, then $Ax = y$.

Well, this was intended as a hint.

More explicitly:

First solve $A^T P^T y = b$ for $y$, which is equivalent to $U^T L^T y = b$.

Then solve $A x = P^T y$ for $x$, premulitplying by $P$ gives $PA x = y$, which is equivalent to $LU x = y$.

Answer 2

Hint: Given that $PA=LU$, take the transpose of each side. That tells you something about $A^T$.