2

Let's assume two real valued matrices $A,B\in R^{w\times d}$ for which $d>w$ and they both have full (column) rank.

I am interested in the invertibility of the Gram matrix $$H(t):=(A+t(B-A))(A+t(B-A))^T$$ for $t\in(0,1)$ (note that $A+t(B-A)$ is the line segment between $A$ and $B$).

If I am correct, there are infinitely many $t$ that $H(t)$ is invertible.

My question is, for which $t$ is $H(t)$ not invertible? Are there finitely many such $t$? I guess based on the polynomial properties of the determinant, it should be finite, right? If yes, can any one help me to prove that?

Mehr
  • 31

1 Answers1

3

Introducing the Gram matrix complicates the problem (and makes computational study of it difficult.) Instead, notice that $H(t)$ is invertible exactly when $A + t(B-A) = A + tC$ is of full rank.

We can study this in detail in terms of the Singular Value Decomposition (SVD) of $A,$

$$A = UDV^\prime,$$

where $U^\prime U = \mathbb{I}_d = VV^\prime$ and $D$ is the diagonal matrix of the $d$ singular values of $A,$ all of which are nonzero because $A$ is of full rank. Accordingly, both $U$ and $V$ are of full rank, so instead let's examine the rank of the $d\times d$ matrix

$$U^\prime H(t) V = D + tU^\prime C V = tD\left(t^{-1}\mathbb{I}_d + D^{-1}U^\prime C V\right),$$

which will be the same as that of $H(t).$ (The rank of $H(0)$ is, of course, the rank of $A,$ so from now on assume $t\ne 0.$)

Taking determinants and writing $p_X(\lambda) = \det(X - \lambda \mathbb I)$ for the characteristic polynomial of any matrix $X,$

$$\begin{aligned} \det \left(U^\prime H(t)V\right) &= \det(tD)\det\left(t^{-1}\mathbb{I}_d + D^{-1}U^\prime C V\right)\\ &=\det(D)\,t^d\ p_{D^{-1}U^\prime (B-A) V}(-t^{-1}). \end{aligned}$$

Since $\det(D)\ne 0$ and $t\ne 0,$ the $t$ for which $H(t)$ is singular are the roots of $p_X(-t^{-1})$ where $X = D^{-1}U^\prime (B-A) V.$

Since the roots of $p_X$ are the eigenvalues of $X,$ we have found that

The only $t$ for which $H(t)$ fails to be invertible are the negative reciprocals of the (nonzero) eigenvalues of $X.$

(This includes complex eigenvalues, BTW.)

Since any $d\times d$ matrix has at most $d$ distinct eigenvalues, there are only finitely many such $t$ -- and we now have a means to compute them all. The ones relevant to the question are the real eigenvalues in the interval $(-\infty, -1),$ which may be fewer in number.

Example

Here is a simple but non-trivial example with $w\times d = 3\times 2$ matrices. Let

$$A = \pmatrix{1&0\\0&1\\0&0},$$

which obviously is of full rank, and

$$B = \pmatrix{-1&-1\\-1&-1\\0&0}.$$

(Although the question stipulates that $B$ should be of full rank, nothing in the foregoing analysis requires that and this example helps show why that is unnecessary.)

Here is R code to assess the invertibility of $H(t)$ by computing its determinant:

detH <- Vectorize(function(x, A, B) det(crossprod(A + x*(B - A))), "x")

I vectorized the calculation to enable easy plotting of $\det (H(t)),$ as in this snippet and its output:

A <- rbind(diag(1,2), 0)
B <- rbind(matrix(-1,2,2), 0)
curve(detH(t, A, B), 0, 1, xname="t", n=501, lwd=2)
abline(v = c(1/3, 1), col="Red", lty=3)

Figure

Evidently $H(t)$ fails to be of invertible precisely when $t\in\{1/3,1\},$ because those are the two points where this graph touches $0.$

What does the analysis say? We must begin with the SVD of $A.$ $A$ already is column-orthogonal, meaning $A=U,$ whence $D=V=\mathbb{I}_2$ are both identity matrices. Thus

$$X = D^{-1}U^\prime (B-A) V = U^\prime (B-A) = \pmatrix{1&0&0\\0&1&0}\pmatrix{-2&-1\\-1&-2\\0&0}=\pmatrix{-2&-1\\-1&-2}.$$

Notice that although $A$ and $B$ are rectangular matrices, $X$ is a square $d\times d$ matrix. Its characteristic polynomial is

$$p_X(\lambda) = \det(X - \lambda\mathbb{I}_2) = \det\pmatrix{-2-\lambda&-1\\-1&-2-\lambda}=(2+\lambda)^2-1.$$

Its zeros all satisfy $(2+\lambda)^2=1,$ whence the eigenvalues are $\lambda\in\{-3,-1\}.$ Their negative reciprocals are $t\in\{1/3,1\},$ agreeing with the direct R calculation.

whuber
  • 322,774
  • Interesting proof idea. Thank you very much. – Mehr Apr 27 '22 at 11:50
  • If I am correct your proof is based on defining $H(t):=A+tC$. Right? And you also considered A,B are squared matrices. Right? But the point is, in the original problem we have $A,B \in R^{w\times d}$ (non squared) that $d \ge w$. Now, I am wondering how to apply your proof for non squared cases. – Mehr Apr 27 '22 at 13:19
  • I made no restriction to square matrices. Everything works for $w\ge d.$ (When $w\lt d,$ it is impossible for $A$ to have full rank.) In fact, when checking this answer before posting it I implemented the calculations in R and tested them on rectangular matrices. If you are unfamiliar with SVD, take a look here. – whuber Apr 27 '22 at 14:49
  • Great response! Thank you so much. – Mehr May 03 '22 at 07:12
  • I am still wondering for the case with $w<d$. Then, $A$ can have full row rank!right? Then, as a wild guess there might be a proof also for this case. But I don't know how? – Mehr May 03 '22 at 08:00
  • If I am correct, we can follow exactly same proof as yours for $w<d$ but instead, we should work with $(A+tC)^T$. – Mehr May 03 '22 at 08:26
  • Yes--just work with the transpose. That's why I didn't dwell on that case. – whuber May 03 '22 at 13:28
  • Great! Thank you for all the help. – Mehr May 03 '22 at 18:07