This is the 1st theoretical post I’m writing on this blog. I’ll review some important Linear Algebra concepts that I’m using at work and these will save you a lot of time if you work with large datasets as I do.

• Diagonalization
• Cayley-Hamilton Theorem
• Time saving steps in R

Diagonalization

Let \(\renewcommand{\vec}[1]{\boldsymbol{#1}} \newcommand{\R}{\mathbb{R}} A=

In general,

If \(A\) can be displayed in a useful factorization of the form \(A = PDP^{-1}\), with \(D\) a diagonal matrix (\(d_{ij} = 0\) if \(i\neq j\)) and \(P\) invertible, then is easy to obtain \(A^k\).

Remember than an eigenvector of \(A\) is a vector \(\vec{v}\in \R^n\) such that \(A\vec{v} = \lambda \vec{v}\) with \(\lambda\) being an eigenvalue of \(A\).

Theorem (Diagonalization Theorem). Let \(A\) an \(n\times n\) matrix. \(A\) is diagonalizable if and only if \(A\) has \(n\) linearly independent eigenvectors. In fact, \(A=PDP^{-1}\), with \(D\) a diagonal matrix and \(P\) an invertible matrix, if and only if the columns of \(P\) are \(n\) linearly independent vectors of \(A\). In this case, the diagonal entries of \(D\) are eigenvalues of \(A\) that correspond to the eigenvectors in \(P\).

Proof. Let \(P \in \R^{n\times n}\) being a matrix of eigenvectors of \(A\) and \(D\) being any diagonal matrix of eigenvalues, then

and

Suppose that \(A\) is diagonalizable, then \(A = PDP^{-1}\) and by multiplying by \(P\) I obtain \(AP = PD\). By replacing the obtained values of \(AP\) and \(PD\) y obtain

Given that \(P\) is invertible, its columns \(\vec{v_1},\ldots,\vec{v_n}\) must be linearly independent. Those columns are also different from \(\vec{0}\), so \(\lambda_1,\ldots,\lambda_n\) are eigenvalues and \(\vec{v_1}, \ldots, \vec{v_n}\) are eigenvectors.

Given any \(n\) eigenvectors of \(A\), let \(P = [\vec{v_1} \: \vec{v_2} \: \ldots \vec{v_n}]\) and \(d_{ij} = \lambda_i\) for \(i = j\) and \(d_{ij} = 0\) in other case. Then \(AP = PD\) is true without imposing conditions on the eigenvectors. If the eigenvectors are linearly independent, then \(P\) is invertible and \(AP = PD\) implies \(A = PDP^{-1}\).

Cayley-Hamilton Theorem

Statement and Proof

Let \(A\in \R^{n\times n}\) the characteristic polynomial of \(A\) is defined as

Theorem (Cayley-Hamilton, 1858). Every square matrix is a root of its own characteristic polynomial.

Proof. Let \(A\in \R^{n\times n}\). The characteristic polynomial of \(A\) is a polinomial of \(\lambda\), its degree is \(n\), and can be written as

Consider the adjoint matrix of \((\lambda I – A)\). By definition of the adjoint, this will be a matrix whose components are monic polinomials of \(\lambda\) and its highest degree is \(n-1\).

Hence, it is possible to write the adjoint as

Where \(B_j \in \R^{n\times n}\) and each \(B_j\) is a constant matrix.

By using adjoint properties I have

By replacing this equation \((*)\) and \((**)\) I obtain

Hence,

By quating similar terms

By summing these last equations I obtain

which concludes the proof.

Application: Obtain the inverse of a matrix

Cayley-Hamilton theorem can be used, among other things, to obtain the inverse of a matrix. To do that I propose three steps.

1st step. Obtain the characteristic polinomial of \(A\) that is defined as

2nd step. Equate the characteristic polinomial to zero and replace \(\lambda\) by \(A\) and attach \(I\) to the terms where there is no replacement. Example:

3rd step. Solve for \(I\) and remember that \(AA^{-1}=I\). Continuing the last example:

Examples

2×2 matrix

Consider the matrix

To obtain the inverse of \(A\) these are the steps:

1st step. Obtain the characteristic polinomial of \(A\) and equate to zero

2nd step. Take the last result and transform by replacing \(\lambda\) by \(A\)

3rd step. Factorize by \(A\) in the equation \(A^2-5A-2I = 0\) and solve for \(I\)

As \(AA^{-1}=I\) I obtain \(A^{-1} = \frac{1}{2} (A-5I)\) and then

4×4 matrix

Here the method proves to be useful.

Consider the matrix

Following the last steps I obtain

By using \(\displaystyle(x+y)^n = \sum_{k=0}^n \frac{n!}{(n-k)!k!} \vec{x}^{n-k}\vec{y}^k\) I obtain

By doing the replacements I obtain

and then \(A^{-1}=-A^3+4A^2-6A+4I\).

Now I obtain the matrix that belongs to the obtained polinomial

And by replacing the obtained matrix I replace in the obtained polinomial and I have the inverse of \(A\)

Time saving steps in R

A <- rbind(c(5,0,0,0),c(0,5,0,0),c(1,4,-3,0),c(-1,2,0,-3))
P <- eigen(A)$vectors
D <- diag(eigen(A)$values)

ptm <- proc.time()
A%*%A

##      [,1] [,2] [,3] [,4]
## [1,]   25    0    0    0
## [2,]    0   25    0    0
## [3,]    2    8    9    0
## [4,]   -2    4    0    9

proc.time() - ptm

##    user  system elapsed 
##   0.003   0.000   0.003

ptm <- proc.time()
P%*%(D%*%D)%*%solve(P)

##      [,1] [,2] [,3] [,4]
## [1,]   25    0    0    0
## [2,]    0   25    0    0
## [3,]    2    8    9    0
## [4,]   -2    4    0    9

proc.time() - ptm

##    user  system elapsed 
##   0.003   0.001   0.007

Final comment

For a small matrix this can be tedious but for a large matrix consider that in some cases you can diagonalize and save a lot of memory if you are using, for example, R o Matlab and you need a really large correlation matrix.