How to prove $\det(I+uv^\intercal)=1+v^\intercal u$

Question

---

Let be $u,v\in\mathbb{R}^n$, then $\det(I+uv^\intercal)=1+v^\intercal u $

where $I$ denotes the identity matrix of order $n$. How to prove this?

---

what I did:

---

let be $A=\{n\in\mathbb{N}: \forall u,v \in \mathbb{R^n}, \det(I+uv^\intercal)\neq1+v^\intercal u \} $, and suppose $A\neq \varnothing $, then for the well-orderer-principle there exists $n_0\in A$ such $n_0\leq n,\;\forall n\in A$. since $1\notin A,\; n_0\neq 1 \rightarrow n_0-1\in\mathbb{N}\setminus A $ so: $$\forall u,v\in\mathbb{R^{n_0-1}}: \det(I+uv^\intercal)=1+v^\intercal u $$

Then, let be $u,v\in\mathbb{R}^{n_0}$, so $$\det(I+uv^\intercal)= \displaystyle\sum_{j=1}^{n_0}(-)^{1+j}a_{1j}\det(A_{1j})$$ where $a_{ij}=\begin{cases} u_iv_j+1 & i=j \\ u_iv_j & i\neq j \end{cases}$, and $A_{1j}$ is the submatrix of $I+uv^\intercal$ that results deleting the i-file and j-column. Then I try to open the term for $j=1$ and try to use the relation for the new matrix of $n_0-1$ order with the determinant because it holds the same form but I have other terms which difficult me the work. Do you know other method?.

Ps. here, in page 2 I've found something similar but I don't understand what it means

PS. I'm taking a course of numerical analisys

Answer 1

You are looking at a special case of the Matrix determinant Lemma. From the Wikipedia page, the proof for the case $A = I$ follows from the equality $$ \begin{bmatrix} I & 0 \\ v^T & 1 \end{bmatrix} \begin{bmatrix} I + uv^T & u \\ 0 &1 \end{bmatrix} \begin{bmatrix} I & 0 \\ -v^T & 1 \end{bmatrix} = \begin{bmatrix} I & u \\ 0 & 1 + v^Tu \end{bmatrix}$$

Answer 2

Hint: $\det(\lambda I -A)=\prod_{i=1}^n (\lambda-\lambda_i) $ where $\lambda_i$ are the eigenvalues of $A$ (with probably multiplicity $>1$). Also note that $uv^T$ has one eigenvalue $v^T u$ and the rest $0$. I think you can proceed from here.

Answer 3

Thought Samrat Mukhopadhyay"s answer is of course in principle correct, it provides no justification for the stated multiplicities of the eigenvalues. In what follows, I have tried to explain, amongst other things, just how these multiplicities arise.

If

$u = 0 \;\; \text{or} \;\; v = 0 \tag{1}$

we have

$uv^T = 0 \tag{2}$

and

$v^Tu = 0; \tag{3}$

then

$\det(I + uv^T) = \det(I) = 1 = 1 + v^Tu; \tag{4}$

thus we may assume

$u \ne 0 \ne v; \tag{5}$

note that

$(uv^T)u = u(v^Tu) = (v^Tu)u, \tag{6}$

which shows that $v^Tu$ is an eigenvalue of $uv^T$ with eigenvector $u$; thus the multiplicity of $v^Tu$ is at least $1$; we will now attempt to find out just when it is precisely $1$, and also to find the other eigenvalues and their multiplicities.

We consider the map

$v^T(\cdot):  \Bbb R^n \to \Bbb R \tag{7}$

given by

$v^T(x) = v^Tx; \tag{8}$

it is manifestly a linear functional on $\Bbb R^n$, that is, $v^T(\cdot) \in \Bbb R^{n*}$, the dual vector space to $\Bbb R^n$.  We note that $v \ne 0$ implies

$v^T(v) = v^Tv \ne 0 \tag{9}$

as well; thus $0 \ne v^T(\cdot) \in \Bbb R^{n*}$; as such, $\ker v^T(\cdot) \subset \Bbb R^n$ is a subspace with

$\dim (\ker v^T(\cdot)) = n - 1. \tag{10}$

Now suppose that

$v^T(u) = v^Tu \ne 0; \tag{11}$

then

$u \notin \ker v^T(\cdot), \tag{12}$

and since

$uv^T(x) = 0 = 0x \tag{13}$

for $0 \ne x \in \ker v^T(\cdot)$, it follows from (6), (10) and (12) that $uv^T$ has a one dimensional-eigenspace $\operatorname{span} \langle u \rangle$ associated with $v^Tu$, and an $n - 1$ dimensional eigenspace $\ker{v^T}$ associated with eigenvalue $0$; thus the multiplicity of $v^Tu$ is $1$ and that of $0$ is $n - 1$.  If, on the other hand,

$v^T(u) = v^Tu = 0, \tag{14}$

that is,

$u \in \ker(v^T(\cdot)), \tag{15}$

then we further note that

$uv^T(v) = u(v^Tv) = (v^Tv)u \in \ker v^T(\cdot), \tag{16}$

whence

$(uv^T)^2(v) = (uv^T)(uv^T)(v) = uv^T((v^Tv)(u)) = (v^Tv) u(v^Tu) = 0. \tag{17}$

Now by virtue of the facts that $v \notin \ker(v^T)$ (cf. (9)) and $\dim (\ker v^T) = n - 1$, we see that

$\Bbb R^n = \ker v^T + \operatorname{span}(\langle v \rangle); \tag{18}$

clearly, $(uv^T)^2 = 0$ on $\ker v^T(\cdot)$, and by what we have just seen, $(uv^T)^2 = 0$ on $\operatorname{span}(\langle v \rangle)$; thus

$(uv^T)^2 = 0 \tag{19}$

when (14) applies.  But (19) implies that every eigenvalue of $uv^T$ must vanish; in fact, from (6), $u$, and hence $(v^Tv)u$, are eigenvectors of $uv^T$ with eigenvalue $0$; whence by (16), $v$ is a generalized eigenvector of $uv^T$ for eigenvalue $0$.  In any event, the above considerations show that $0$ is an eigenvalue of $uv^T$ with multiplicity $n$ provided (14) binds.

We bring all these observations together to reach the desired conclusion. The case (1) is first and most easily dispensed with, as has been done in (4). The case (5) breaks into the two sub-cases (11) and (14); in (11), $uv^T$ has eigenvalues $v^Tu$ of multiplicity one and $0$ of multiplicity $n - 1$; thus $I + uv^T$ has eigenvalues $1 + v^Tu$ of multiplicity one and $1$ of multiplicity $n - 1$; using the fact that the determinant of a matrix is the product of its eigenvalues, we find

$\det(I + uv^T) = 1^{n - 1} (1 + v^Tu) = 1 + v^Tu; \tag{20}$

as for case (14), $uv^T$ has only eigenvalue $0$ of multiplicity $n$; thus $1 + uv^T$ has only eigevalue $1$ of multiplicity $n$; then

$\det(I + uv^T) = 1^n = 1 = 1 + v^Tu, \tag{21}$

by (14).

Thus we see that, in all cases,

$\det(I + uv^T) = 1 + v^Tu, \tag{22}$

as was to be shown. QED.