16
$\begingroup$

My professor always writes on the board:

$A$ is $m \times n$, assuming that the vectors of $A$ form a basis, then $A^TA$ is always invertible.

one thing I know is that $A^TA$ is always symmetric, but I'm not sure about the conditions on a symmetric matrix needed to ensure that it is invertible?

$\endgroup$
9
  • 3
    $\begingroup$ What do you nean by "the vectors for $A$"? $\endgroup$ Jul 9, 2017 at 17:38
  • $\begingroup$ Sorry, should be "vectors of A" - it's my english. $\endgroup$
    – makansij
    Jul 9, 2017 at 17:49
  • 1
    $\begingroup$ There is a long list of conditions that are equivalent to the condition that a matrix is invertible, all of which are equally valid for symmetric matrices. Are you instead asking for conditions on a matrix $A$ to ensure that $A^TA$ is invertible? $\endgroup$
    – JMoravitz
    Jul 9, 2017 at 17:55
  • 1
    $\begingroup$ The words you need are "row" and "column." With $m$ rows and $n$ columns, we find $A^T A$ is a square of size $n.$ When $m \geq n$ and the $n$ columns of $A$ are independent, then $A^T A$ is also of rank $n,$ therefore invertible. $\endgroup$
    – Will Jagy
    Jul 9, 2017 at 17:56
  • $\begingroup$ @JMoravitz yes, sorry perhaps mis-asked the question, thank you. $\endgroup$
    – makansij
    Jul 10, 2017 at 5:27

2 Answers 2

11
$\begingroup$

A sufficient condition for a symmetric $n\times n$ matrix $C$ to be invertible is that the matrix is positive definite, i.e. $$\forall x\in\mathbb{R}^n\backslash\{0\}, x^TCx>0.$$

We can use this observation to prove that $A^TA$ is invertible, because from the fact that the $n$ columns of $A$ are linear independent, we can prove that $A^T A$ is not only symmetric but also positive definite.

In fact, using Gram-Schmidt orthonormalization process, we can build a $n\times n$ invertible matrix $Q$ such that the columns of $AQ$ are a family of $n$ orthonormal vectors, and then: $$I_n=(AQ)^T (AQ)$$ where $I_n$ is the identity matrix of dimension $n$.

Get $x\in\mathbb{R}^n\backslash\{0\}$.

Then, from $Q^{-1}x\neq 0$ it follows that $\|Q^{-1}x\|^2>0$ and so: $$x^T(A^TA)x=x^T(AI_n)^T(AI_n)x=x^T(AQQ^{-1})^T(AQQ^{-1})x \\ = x^T(Q^{-1})^T(AQ)^T(AQ)(Q^{-1}x) = (Q^{-1}x)^T\left((AQ)^T(AQ)\right)(Q^{-1}x) \\ = (Q^{-1}x)^TI_n(Q^{-1}x) = (Q^{-1}x)^T(Q^{-1}x) = \|Q^{-1}x\|^2>0.$$ Being $x$ arbitrary, it follows that: $$\forall x\in\mathbb{R}^n\backslash\{0\}, x^T(A^TA)x>0,$$ i.e. $A^TA$ is positive definite, and then invertible.

$\endgroup$
3
  • 5
    $\begingroup$ Why do you need to use Gram-Schmidt? You can argue directly that $x^T A^T Ax = (Ax)^T (Ax) = \|Ax\|^2$, and the RHS is strictly positive for all nonzero $x$ provided that $A$ has trivial null space (or equivalently, that $A$ has full column rank). $\endgroup$
    – user169852
    Aug 27, 2018 at 16:04
  • $\begingroup$ What is the connection between positive definiteness and the determinant being different from zero? $\endgroup$
    – asd11
    Jan 20, 2019 at 10:47
  • 1
    $\begingroup$ @asd11 eigen values > 0, which implies $\prod \lambda = det A > 0$ $\endgroup$ Apr 25, 2021 at 15:23
1
$\begingroup$

@RobertLewis

A Gram matrix is usually defined by giving a set of vectors and then defining the i,j entry as the dot product of the i,j vectors. In doing so, clearly the set of vectors can be thought of as column vectors of A. So saying "the vectors for A" is a completely natural thing to say, and should be unambiguous.

here is an elegant proof Gram matrix invertible iff set of vectors linearly independent

$\endgroup$
4
  • $\begingroup$ you seem to be saying that the ONLY condition needed on $A$ for $A^TA$ to be invertible is if the column vectors of $A$ are linearly independent. Please look at the example I gave to YvesDaoust: if A is composed of those two vectors I just mentioned $([0,1,0,0], [1,0,0,1])$ , then $A^TA$ is symmetric but not invertible. So, I think that your claim is not entirely true. $\endgroup$
    – makansij
    Jul 17, 2017 at 0:41
  • 2
    $\begingroup$ In your "counterexample", $A^TA = diag(1, 2)$ is most certainly invertible.... $\endgroup$
    – Randy
    Dec 19, 2017 at 21:04
  • 1
    $\begingroup$ @Randy I think nundo probably meant to put a transpose on those two vectors, so that A is a 4x2 matrix, not 2x4. $\endgroup$
    – Confounded
    May 10, 2018 at 17:49
  • $\begingroup$ yes that's correct. thanks $\endgroup$
    – makansij
    Sep 15, 2018 at 23:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .