8
$\begingroup$
  • If $A$ is any $n \times m$ matrix and $B$ is any $m \times n$ matrix then one familiar form of the Sylvester's identity is $\det(I + AB) = \det(I + BA)$.

    Now somehow curiously this above identity is often enough used along side another statement which says that for any vector $v$ and any invertible square matrix $A$, it is true that $\det(A + v v^T) = \det(A)\det(I + v^TA^{-1}v)$.

    Is there some relationship between these two identities? Like can one be gotten from the other or vice versa?

  • A particularly useful (at least in some recent big breakthrough researches!) form of the Sylvester's identity is when $A= tu, B = v^\dagger $ where ($u$ and $v$ are complex vectors and $t$ is some complex number). This then shows that $\det(I + t u v^\dagger) = 1 + tv^\dagger u$

Now this simple statement above apparently implies this more powerful formulation which is not clear to me - If $C$ is any $n\times n$ (necessarily invertible?) matrix and $A$ is a rank-$1$ matrix then is $\det( I + tCA)$ is a degree $1$ polynomial in $t$? Why? (and this is the same as saying that this is "affine-linear" in t?)

$\endgroup$

2 Answers 2

12
$\begingroup$

For the first point, note that by Sylvester's identity

$$\det(I_1 + v^TA^{-1}v) = \det(I_1 + (v^T)(A^{-1}v)) = \det(I_n+(A^{-1}v)(v^T)) = \det(I_n + A^{-1}vv^T),$$

so

$$\det(A)\det(I_1+v^TA^{-1}v) = \det(A)\det(I_n + A^{-1}vv^T) = \det(A + vv^T).$$

Given $u \in \mathbb{R}^m$ and $v \in \mathbb{R}^n$, their outer product is the $m\times n$ matrix $uv^T$. If $u$ and $v$ are non-zero, then their outer product has rank one. Conversely, a rank one $m\times n$ matrix can be written as the outer product of some non-zero $u$ and $v$.

Now suppose $C$ is an $n\times n$ matrix (not necessarily invertible) and $A$ is a rank one $n\times n$ matrix. By the above discussion, there are $u, v \in \mathbb{R}^n$ such that $A = uv^T$. So

\begin{align*} \det(I_n + tCA) &= \det(I_n + tCuv^T)\\ &= \det(I_n + (tCu)(v^T))\\ &= \det(I_1 + (v^T)(tCu))\\ &= \det(I_1 + tv^TCu)\\ &= 1 + tv^TCu \end{align*}

where the last equality follows because $I_1 + tv^TCu$ is a $1\times 1$ matrix.

A function of the form $f(t) = at + b$ is called affine. I'm guessing this is what is meant by affine-linear.

Added Later: Let me add a theorem which further demonstrates the relationship between the rank of a matrix and outer products. In the following statement, I am taking the definition of the rank of a matrix to be the dimension of its column space.

Theorem: An $m\times n$ matrix $A$ has rank $k$ if and only if the minimal number of outer products needed to express $A$ as a sum is $k$ (i.e. $A$ can be written as the sum of $k$ outer products, but not $k - 1$).

Proving this is a really nice exercise in elementary linear algebra. I would hate to rob you of the experience by posting the solution here.

$\endgroup$
6
  • $\begingroup$ So the crucial thing here seems to be the fact that "A rank one m×n matrix can be written as the outer product of some non-zero u and v." Can you kindly reference this? $\endgroup$
    – Student
    Nov 10, 2014 at 5:50
  • 5
    $\begingroup$ @Anirbit: that is more or less the definition of being rank one. $\endgroup$ Nov 10, 2014 at 7:31
  • $\begingroup$ @QiaochuYuan :'( That is somehow not very familiar to me. Can you sketch the argument may be? $\endgroup$
    – Student
    Nov 10, 2014 at 8:52
  • 1
    $\begingroup$ @Anirbit Let $S$ be an $m \times n$ matrix of rank $1$. By the rank-nullity theorem, the nullity of $S$ is $(n-1)$, and hence the orthogonal complement of the nullspace of $S$ is $1$-dimensional; pick a unit vector $v$ in the orthogonal complement of the nullspace of $S$. You can then check that $S = uv^T$ for $u := Sv$. $\endgroup$ Nov 10, 2014 at 10:08
  • 1
    $\begingroup$ @passerby51: You're right. Thanks. $\endgroup$ Mar 2 at 18:11
8
$\begingroup$

The common ground of those two formulas is related to the Woodbury matrix identity. This relation is a useful statement that shows what happens to the inverse when one "updates" a matrix $A\in\mathbb{C}^{n\times n}$ with a term $UCV$, with $U,V\in\mathbb{C}^{n\times m}$, $C\in\mathbb{C}^{m\times m}$. The typical situation is when $m<n$ and this update is a small-rank term. The rank-1 version, often useful in its own, is called Sherman–Morrison formula.

A statement on determinants can be derived with a small modification to the proof: take Equations (1) and (2) here; compute determinants of the first and third member of those chains of equalities, and equate them: $$ \det A^{-1}\det(C-VA^{-1}U)^{-1} = \det\begin{bmatrix}A & U\\V&C\end{bmatrix}^{-1} = \det(A-UC^{-1}V)^{-1}\det C^{-1}; $$ invert everything and you get $$ \det A \det(C-VA^{-1}U) = \det(A-UC^{-1}V)\det C, \tag{*}\label{186699_star} $$ which by continuity holds also when $\begin{bmatrix}A & U\\V&C\end{bmatrix}$ isn't invertible. Your two formulas can be derived easily from this one ($C=I$ in both cases).

Equation \eqref{186699_star} is also known as (the two versions of) the Schur complement formula; an equivalent statement appears for instance in the Wikipedia article here (last equation of the section titled Background).

People in applied linear algebra often prefer talking about inverses than determinants, but it's essentially the same result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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