6
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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}$$

$\endgroup$
1
  • $\begingroup$ Thanks, I see the solution now. $\endgroup$ – Luis Felipe Jul 8 '15 at 16:33
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ You are right, thank you!!. but, to show $uv^\intercal$ has one eigenvalue $v^tu$ must I do calculate or there is a fast way to prove this? $\endgroup$ – Luis Felipe Jul 8 '15 at 16:01
  • 5
    $\begingroup$ Just observe that $$uv^T(au)=(v^Tu)au\ \forall a\in \mathbb{R}$$ $\endgroup$ – Samrat Mukhopadhyay Jul 9 '15 at 6:39
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This answer is great. Thank you! $\endgroup$ – Luis Felipe Jul 10 '15 at 3:20
  • $\begingroup$ @LuisFelipeVillavicencioLopez: hey, thank you! $\endgroup$ – Robert Lewis Jul 10 '15 at 3:23

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.