1

Say I have a symmetric $M \times M$ matrix with unit diagonal. For example with $M=4$: $$ \mathbf{A} = \left[\begin{array}{cccc} 1 & a & b & c \\ a & 1 & c & d \\ b & c & 1 & e \\ c & d & e & 1 \end{array}\right] $$ What way do you think is the easiest to show that this is an invertible matrix/has full rank? I have thought about showing that its determinant is always nonzero but the expression for the determinant becomes very intangible as $M$ is increased..

Oh and we can assume that the elements on the off-diagonal are not $1$ and they are positive. To make it clear, I actually have a matrix where $\mathbf{A}_{ij} = \exp(- \alpha \lVert c_i - c_j \rVert^2)$ where $\alpha$ is positive and all $c$s are different.

That Guy
  • 1,309

1 Answers1

1

Note: This is an incomplete answer

The general result you are looking for does not hold. For example, there exists a matrix for $M = 4$ with $$ a = 3/10, \quad b = 2/10, \quad d = 9/10, \quad e = 4/10 $$ that fails to have full rank.

As I note in my comments, the approach laid out below only works for the matrix that you describe, i.e. the matrix with entries $\mathbf{A}_{ij} = \exp(- \alpha \lVert c_i - c_j \rVert^2)$. In fact, I'm having trouble generalizing this argument (since I'm not sure what necessary changes are being referred to here), so I'll stick to the case where $c_1,\dots,c_M \in \Bbb R$.

In order to show that a positive semidefinite matrix is positive definite, it suffices to show that for all non-zero vectors $x\in \Bbb R^M$, we have $x^TAx > 0$. Noting (as in this answer) that $\mathbf A_{ij} = E[e^{i(c_i - c_j)Z}]$, where $Z$ is a random variable with an $N(0,1)$ distribution. As the linked answer demonstrates, we have $$ x^T \mathbf A x = \sum_{j,k=1}^M x_jx_k\mathbf A_{ij} = E\left[\left|\sum_{j=1}^M x_j e^{ic_j Z}\right|^2\right]. $$ Thus, it suffices to show that for $x \neq 0$, this expectation is non-zero. To this end, it suffices to show that if $x \neq 0$, then there exists at least one value of $t \in \Bbb R$ for which $\sum_{j=1}^M x_j e^{ic_j t} \neq 0$.

Ben Grossmann
  • 225,327
  • Thank you! But why does this mean that the matrix has full rank? – That Guy Apr 19 '22 at 22:21
  • @UkulaUdan As I say in my post: in order to show that a positive semidefinite matrix is positive definite (i.e. of full rank), it suffices to show that for all non-zero vectors $x\in \Bbb R^M$, we have $x^TAx > 0$. Are you asking why this is true? – Ben Grossmann Apr 19 '22 at 22:23
  • Yes, why is that true? – That Guy Apr 19 '22 at 22:24
  • To be specific: why is it true that showing that a positive semidefinite matrix is positive definite means that the matrix has independent columns/has full rank? – That Guy Apr 19 '22 at 22:26
  • @UkulaUdan There are a few approaches you can take here. In this post, I show that for a positive semidefinite $A$, $Ax = 0 \iff x^TAx = 0$ in a few different ways. Alternatively, it suffices to note that $A$ has full rank iff its determinant is non-zero, which holds iff its eigenvalues are non-zero (since the determinant is the product of eigenvalues), which holds iff $A$ is positive definite. – Ben Grossmann Apr 19 '22 at 22:30
  • The last part was the key I have been missing! But how would you go about actually finding that $t$ value? – That Guy Apr 19 '22 at 22:42
  • @UkulaUdan scroll down and look at the "solutions" – Ben Grossmann Apr 19 '22 at 23:24