Let $A_{j,k} = \langle x_j, x_k\rangle$. Show $A$ is invertible if and only if $x_1, \ldots, x_n$ are linearly independent.

Question

Let $V$ be a vector space over $\mathbb C$ with inner product $\langle, \rangle$ and let $x_1, \ldots, x_n$ be vectors in $V$.

Consider the $n \times n$-matrix $A$ with entries $A_{j,k} = \langle x_j, x_k\rangle$.

I want to show that $A$ is invertible if and only if $x_1, \ldots, x_n$ are linearly independent.

I know that orthogonal vectors are linearly independent, so if $x_1, \ldots, x_n$ where orthogonal the result is easily proven. However, the general case I'm stuck at.

Answer 1

In order to simplify the notation, set $A_{jk}=\langle x_k,x_j\rangle$ instead. Since $A$ is Hermitian, it does not really matter. If you insist on using "your" $A$, just replace $A$ with $\bar{A}$ everywhere.

Let $y:=[\eta_1,\ldots,\eta_n]^T$ denote a vector in $\mathbb{C}^n$. Let $x_1,\ldots,x_n$ be linearly dependent. Then for some $y\in\mathbb{C}^n\setminus\{0\}$, $\eta_1x_1+\cdots+\eta_nx_n=0$. Making products with $x_j$ gives $$ \eta_1\langle x_1,x_j\rangle+\cdots+\eta_n\langle x_n,x_j\rangle=0, \quad j=1,\ldots,n, $$ which is equivalent to $Ay=0$. Since $y\neq 0$, it follows that $A$ is singular.

Note that $$\tag{$*$}\langle\eta_1x_1+\cdots+\eta_nx_n,\eta_1x_1+\cdots+\eta_nx_n\rangle =\sum_{i,j=1}^n\eta_i\bar{\eta_j}\langle x_i,x_j\rangle=y^*Ay$$ is zero if and only if $\eta_1x_1+\cdots+\eta_nx_n=0$ (because the left-hand side of ($*$) is the square of the norm induced by the inner product). If $A$ is singular, again, there is a nonzero $y$ such that $Ay=0$. Therefore, $y^*Ay=0$ and using ($*$) it follows that $x_1,\ldots,x_n$ are linearly dependent.

Answer 2

Let $$ B=\begin{bmatrix} x_{1,1}&x_{2,1}&x_{3,1}&\cdots&x_{n,1}\\ x_{1,2}&x_{2,2}&x_{3,2}&\cdots&x_{n,2}\\ x_{1,3}&x_{2,3}&x_{3,3}&\cdots&x_{n,3}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ x_{1,n}&x_{2,n}&x_{3,n}&\cdots&x_{n,n}\\ \end{bmatrix} $$ where the $k^{\text{th}}$ column is $x_k$. Then $$ A=B^T\overline{B} $$ We have $$ A\overline{x}=0\implies B^T\overline{Bx}=0\implies x^TB^T\overline{Bx}=0\implies Bx=0 $$ and $$ Bx=0\implies B^T\overline{Bx}=0\implies A\overline{x}=0 $$ Thus, $A\overline{x}=0\iff Bx=0$; that is, $A$ is singular if and only if the columns of $B$ are dependent.