3
$\begingroup$

I am trying to prove that if $u_i\in \mathbb{R}$ for $i=1,...,n$ and $$X =\begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \ & \vdots & \ & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ u_1 & u_2 & u_3 & \cdots & u_n \end{pmatrix}$$

then $\det(X^{T}X)=1 +u_1^2 + u_2^2 + \cdots + u_n^2$, where $X^T$ is the transpose of $X$.

Here is what I know. $X$ is an $(n+1)$-by-$n$ matrix, and $X^T$ is an $n$-by-$(n+1)$ matrix; thus $X^TX$ is an $n$-by-$n$ square matrix, so we can take its determinant.

Also, the formula is simple to verify for the cases $n=2,3$.

The $(i,j)$ entry of the matrix $X^TX$ is \begin{align*} (X^TX)_{i,j} &= \sum_{k}(X^T)_{i,k}X_{k,j} = \sum_k X_{k,i}X_{k,j} \\ &= \langle X_{\cdot,i},X_{\cdot, j} \rangle = \delta_{i,j} + u_iu_j \end{align*} where $X_{\cdot,j}$ denotes the $j$th column of $X$. Since I know all the entries, I could do some combination of induction and cofactor expansion, but I couldn't make it work.

I also tried computation with "block" matrices, which is something I am not very familiar with. If $I_n$ is the $n$-by-$n$ identity matrix and $\vec{u}=(u_1,\ldots,u_n)$ then we have $$ \vec{u} = \begin{pmatrix} u_1 \\ u_2 \\ \vdots \\ u_n \end{pmatrix} \;\;\; \text{ and}\;\;\; \left( \vec{u}\right)^T = \begin{pmatrix} u_1 & u_2 & \cdots & u_n\end{pmatrix} $$ so that $$ X^T = \begin{pmatrix} I_n & \vec{u} \end{pmatrix} \;\;\; \text{ and}\;\;\; X = \begin{pmatrix} I_n \\ \left(\vec{u}\right)^T \end{pmatrix}. $$

Then if we are presumptuous, we can treat $X^T$ and $X$ as $1$-by-$2$ and $2$-by-$1$ matrices respectively. Then $$ X^TX = 1 + \vec{u}\left(\vec{u} \right)^T = 1 + \|u\|^2 $$ which clearly would imply the result I want, if this computation can be justified.

I was unable to find this specific problem elsewhere, but I am sure it has been asked other times on this site.

Please let me know your thoughts and tips for this problem, and help me justify or refute the block matrix computation I performed. If we cannot justify it, then why does it hint at the right answer? Thanks.

$\endgroup$
  • 2
    $\begingroup$ The bug in your logic is, in block multiplication you get $uu^T \ne u^T u = \|u\|$... In particular, $uu^T$ is a matrix, not a number $\endgroup$ – gt6989b May 28 at 17:21
  • $\begingroup$ I see my mistake; I made the classic error of trying to force the result I wanted... How can I compute this determinant without brute-force? $\endgroup$ – Caleb Nastasi May 28 at 17:25
4
$\begingroup$

You may use the identity $\det(I+AB)=\det(I+BA)$, where the $I$ on the LHS has the same size as $AB$ and the $I$ on RHS has the same size as $BA$. This identity follows from the fact that $AB$ and $BA$ have the same set (counting multiplicities) of nonzero eigenvalues over the algebraic closure of the underlying field.

In you case, the identity gives $\det(I_n+uu^T)=\det(I_1+u^Tu)=1+\|u\|^2$.

$\endgroup$
  • $\begingroup$ +1, very cool identity, never thought about it $\endgroup$ – gt6989b May 28 at 19:33
  • $\begingroup$ +1, this is an elegant solution! $\endgroup$ – Maximilian Janisch May 28 at 19:54
4
$\begingroup$

You can use a LU-decomposition (where an "empty sum" is considered as $0$): \begin{align} X^\top X&=LU \text{, where} \\ U_{i,j}&= \begin{cases} 1+\sum_{k=1}^j u_k^2 &, \text{ if } i=j; \\ u_i u_j &,\text{ if } j > i \text{ (upper triangular part)}; \\ 0 &, \text{ if } j < i \end{cases} \\ L_{i,j}&= \begin{cases} \dfrac{1}{1+\sum_{k=1}^{j-1} u_k^2}&, \text{ if } i=j; \\ u_i u_j\cdot\left(\displaystyle\prod_{k=j-1}^j\Big(1+\sum_{h=1}^k u_k^2\Big)\right)^{-1} &, \text{ if } i<j \text{ (lower triangular part)}; \\ 0 &, \text{ if } i>j; \end{cases} \end{align}

We thus have, by multiplicity of the determinant, $\det(X^\top X)=\det(L)\det(U)$. Since $L$ has only $0$s in its upper part, and $U$ has only $0$s in its lower part, the determinant of these matrices is simply the product of their diagonal elements. Thus,

\begin{equation}\begin{split} \det(X^\top X)&=\det(L)\det(U) \\&= \prod_{h=1}^n\left(1+\sum_{k=1}^h u_k^2\right)\cdot \prod_{h=1}^n\left(\frac1{1+\sum_{k=1}^{h-1} u_k^2}\right) \\ &= \prod_{h=1}^n\frac{1+\sum_{k=1}^h u_k^2}{1+\sum_{k=1}^{h-1} u_k^2} \\ &= 1+\sum_{k=1}^n u_k^2 \qquad\text{(by cancellation of terms)}. \end{split}\end{equation}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.