3.6 Linear Algebra

Linear algebra is extensively used in applied quantitative finance because of its role in statistics, optimization, Monte Carlo simulation, signal processing, etc. Not surprisingly, it is also a comprehensive mathematical field that covers many topics. In this section, we discuss several topics that have significant applications in statistics and numerical methods.

Vectors

An $n\times1$ (column) vector is a one-dimensional array. It can represent the coordinates of a point in the $R^n$ ($n$-dimensional) Euclidean space.

Inner product/dot product: the inner product (or dot product) of two $R^n$ vectors $x$ and $y$ is defined as $\displaystyle\sum_{i=1}^nx_iy_i=x^Ty$

Euclidean norm: $\displaystyle\|x\|=\sqrt{\sum_{i=1}^nx_i^2}=\sqrt{x^Tx};\ \|x-y\|=\sqrt{(x-y)^T(x-y)}$

Then angle $\theta$ between $R^n$ vectors $x$ and $y$ has the property that $\displaystyle\cos\theta=\frac{x^Ty}{\|x\|\|y\|}$. $x$ and $y$ are orthogonal if $x^Ty=0$. The correlation coefficient of two random variables can be viewed as the cosine of the angle between them in Euclidean space ($\rho=\cos\theta$).

There are 3 random variables $x$, $y$ and $z$. The correlation between $x$ and $y$ is 0.8 and the correlation between $x$ and $z$ is 0.8. What is the maximum and minimum correlation between $y$ and $z$?

Solution: We can consider random variables $x$, $y$ and $z$ as vectors. Let $\theta$ be the angle between $x$ and $y$, then we have $\cos\theta=\rho_{x,y}=0.8$. Similarly the angle between $x$ and $z$ is $\theta$ as well. For $y$ and $z$ to have the maximum correlation, the angle between them needs to be the smallest. In this case, the minimum angle is 0 (when vector $y$ and $z$ are in the same direction) and the correlation is 1. For the minimum correlation, we want the maximum angle between $y$ and $z$, which is the case shown in Figure 3.2.

If you still remember some trigonometry, all you need is that

Otherwise, you can solve the problem using Pythagoras’s Theorem:

QR decomposition

QR decomposition: For each non-singular $n\times n$ matrix $A$, there is a unique pair of orthogonal matrix $Q$ and upper-triangular matrix $R$ with positive diagonal elements such that $A=QR$.¹⁰

QR decomposition is often used to solve linear systems $Ax=b$ when $A$ is a non-singular matrix. Since $Q$ is an orthogonal matrix, $Q^{-1}=Q^T$ and $QRx=b\Rightarrow Rx=Q^Tb$. Because $R$ is an upper-triangular matrix, we can begin with $x_n$ (the equation is simply $R_{n,n}x_n=(Q^Tb)_n$), and recursively calculate all $x_i$, $\forall i=n,n-1,\cdots,1$.

If the programming language you are using does not have a function for the linear least squares regression, how would you design an algorithm to do so?

Solution: The linear least squares regression is probably the most widely used statistical analysis method. Let’s go over a standard approach to solving linear least squares regressions using matrices. A simple linear regression with $n$ observations can be expressed as

$y_i=\beta_0x_{i,0}+\beta_1x_{i,1}+\cdots+\beta_{p-1}x_{i,p-1}+\varepsilon_i,\ \forall i=1,\cdots,n$, where $x_{i0}\equiv1,\ \forall i$, is the intercept term and $x_{i,1},\cdots,x_{i,p-1}$ are $p-1$ exogenous regressors.

The goal of the linear least squares regression is to find a set of $\beta=[\beta_0,\beta_1,\cdots,\beta_{p-1}]^T$ that makes $\sum_{i=1}^n\varepsilon_i^2$ the smallest. Let’s express the linear regression in matrix format:

$Y=X\beta+\varepsilon$, where $Y=[Y_1,Y_2,\cdots,Y_n]^T$ and $\varepsilon=[\varepsilon_1,\varepsilon_2,\cdots,\varepsilon_n]^T$ are both $n\times1$ column vectors; $X$ is a $n\times p$ matrix with each column representing a regressor (including the intercept) and each row representing an observation. Then the problem becomes

To minimize the function $f(\beta)$, taking the first derivative¹¹ of $f(\beta)$ with respect to $\beta$, we have $f'(\beta)=2X^T(Y-X\beta)=0\Rightarrow(X^TX)\hat\beta=X^TY$, where $(X^TX)$ is a $p\times p$ symmetric matrix and $X^TY$ is a $p\times1$ column vector.

Let $A=(X^TX)$ and $b=X^TY$, then the problem becomes $A\hat\beta=b$, which can be solved using QR decomposition as we described.

Alternatively, if the programming language has a function for matrix inverse, we can directly calculate $\hat\beta$ as $\hat\beta=(X^TX)^{-1}X^TY$.¹²

Since we are discussing linear regressions, it’s worthwhile to point out the assumptions behind the linear least squares regression (a common statistics question at interviews):

1. The relationship between $Y$ and $X$ is linear: $Y=X\beta+\varepsilon$.
2. $E[\varepsilon_i]=0,\ \forall i=1,\cdots,n$.
3. $\operatorname{var}(\varepsilon_i)=\sigma^2,\ i=1,\cdots,n$ (constant variance), and $E[\varepsilon_i\varepsilon_j]=0,\ i\ne j$ (uncorrelated errors).
4. No perfect multicollinearity: $\rho(x_i,x_j)\ne\pm1,\ i\ne j$ where $\rho(x_i,x_j)$ is the correlation of regressors $x_i$ and $x_j$.
5. $\varepsilon$ and $x_i$ are independent.

Surely in practice, some of these assumptions are violated and the simple linear least squares regression is no longer the best linear unbiased estimator (BLUE). Many econometrics books dedicate significant chapters to addressing the effects of assumption violations and corresponding remedies.

Determinant, eigenvalue and eigenvector

Determinant: Let $A$ be an $n\times n$ matrix with elements $\{A_{i,j}\}$, where $i,j=1,\cdots,n$. The determinant of $A$ is defined as a scalar: $\det(A)=\sum_p\psi(p)a_{1,p_1}a_{2,p_2}\cdots a_{n,p_n}$, where $p=(p_1,p_2,\cdots,p_n)$ is any permutation of $(1,2,\cdots,n)$; the sum is taken over all $n!$ possible permutations; and

For example, determinants of $2\times2$ and $3\times3$ matrices can be calculated as

¹³

Determinant properties: $\det(A^T)=\det(A),\ \det(AB)=\det(A)\det(B),\ \displaystyle\det(A^{-1})=\frac{1}{\det(A)}$

Eigenvalue: Let $A$ be an $n\times n$ matrix. A real number $\lambda$ is called an eigenvalue of $A$ if there exists a nonzero vector $x$ in $R^n$ such that $Ax=\lambda x$. Every nonzero vector $x$ satisfying this equation is called an eigenvector of $A$ associated with the eigenvalue $\lambda$.

Eigenvalues and eigenvectors are crucial concepts in a variety of subjects such as ordinary differential equations, Markov chains, principal component analysis (PCA), etc. The importance of determinant lies in its relationship to eigenvalues/eigenvectors.¹⁴

The determinant of matrix $A-\lambda I$, where $I$ is an $n\times n$ identity matrix with ones on the main diagonal and zeros elsewhere, is called the characteristic polynomial of $A$. The equation $\det(A-\lambda I)=0$ is called the characteristic equation of $A$. The eigenvalues of $A$ are the real roots of the characteristic equation of $A$. Using the characteristic equation, we can also show that $\lambda_1\lambda_2\cdots\lambda_n=\det(A)$ and $\sum_{i=1}^n\lambda_i=\operatorname{trace}(A)=\sum_{i=1}^nA_{i,i}$.

$A$ is diagonalizable if and only if it has linearly independent eigenvectors.¹⁵ Let $\lambda_1,\ \lambda_2,\ \cdots,\ \lambda_n$ be the eigenvalues of $A$, $x_1,\ x_2,\ \cdots,\ x_n$ be the corresponding eigenvectors. and $X=[x_1\mid x_2\mid\cdots\mid x_n]$, then

If matrix $\displaystyle A=\begin{bmatrix}2&1\\1&2\end{bmatrix}$, what are the eigenvalues and eigenvectors of $A$?

Solution: This is a simple example of eigenvalues and eigenvectors. It can be solved using three related approaches:

Approach A: Apply the definition of eigenvalues and eigenvectors directly.

Let $\lambda$ be an eigenvalue and $\displaystyle x=\begin{bmatrix}x_1\\x_2\end{bmatrix}$ be its corresponding eigenvector. By definition, we have

So either $\lambda=3$, in which case $x_1=x_2$ (plug $\lambda=3$ into equation $2x_1+x_2=\lambda x_1$) and the corresponding normalized eigenvector is $\displaystyle\begin{bmatrix}1/\sqrt{2}\\1/\sqrt{2}\end{bmatrix}$, or $x_1+x_2=0$, in which case the normalized eigenvector is $\displaystyle\begin{bmatrix}1/\sqrt{2}\\-1/\sqrt{2}\end{bmatrix}$ and $\lambda=1$ (plug $x_2=-x_1$ into equation $2x_1+x_2=\lambda x_1$).

Approach B: Use equation $\det(A-\lambda I)=0$.

$\det(A-\lambda I)=0\Rightarrow(2-\lambda)(2-\lambda)-1=0$. Solving the equation, we have $\lambda_1=1$ and $\lambda_2=3$. Applying the eigenvalues to $Ax=\lambda x$, we can get the corresponding eigenvectors.

Approach C: Use equations $\lambda_1\cdot\lambda_2\cdots\lambda_n=\det(A)$ and $\sum_{i=1}^n\lambda_i=\operatorname{trace}(A)=\sum_{i=1}^nA_{i,i}$.

$\det(A)=2\times2-1\times1=3$ and $\operatorname{trace}(A)=2\times2=4$.

So we have $\displaystyle\left.\begin{aligned}\lambda_1\times\lambda_2&=3\\\lambda_1+\lambda_2&=4\end{aligned}\right\}\Rightarrow\begin{cases}\lambda_1=1\\\lambda_2=3\end{cases}$. Again apply the eigenvalues to $Ax=\lambda x$, and we can get the corresponding eigenvectors.

Positive semidefinite/definite matrix

When $A$ is a symmetric $n\times n$ matrix, as in the cases of covariance and correlation matrices, all the eigenvalues of $A$ are real numbers. Furthermore, all eigenvectors that belong to distinct eigenvalues of $A$ are orthogonal.

Each of the following conditions is a necessary and sufficient condition to make a symmetric matrix $A$ positive semidefinite:

1. $x^TAx\ge0$ for any $n\times1$ vector $x$.
2. All eigenvalues of $A$ are nonnegative.
3. All the upper left (or lower right) submatrices $A_K,\ K=1,\cdots,n$ have nonnegative determinants.¹⁶

Covariance/correlation matrices must also be positive semidefinite. If there is no perfect linear dependence among random variables, the covariance/correlation matrix must also be positive definite. Each of the following conditions is a necessary and sufficient condition to make a symmetric matrix $A$ positive definite:

1. $x^TAx>0$ for any nonzero $n\times1$ vector $x$.
2. All eigenvalues of $A$ are positive.
3. All the upper left (or lower right) submatrices $A_K,\ K=1,\cdots,n$ have positive determinants.

There are 3 random variables $x$, $y$ and $z$. The correlation between $x$ and $y$ is 0.8 and the correlation between $x$ and $z$ is 0.8. What is the maximum and minimum correlation between $y$ and $z$?

Solution: The problem can be solved using the positive semidefiniteness property of the correlation matrix.

Let the correlation between $y$ and $z$ be $\rho$, then the correlation matrix for $x$, $y$ and $z$ is

So the maximum correlation between $y$ and $z$ is 1, the minimum is 0.28.

LU decomposition and Cholesky decomposition

Let $A$ be a nonsingular $n\times n$ matrix. LU decomposition expresses $A$ as the product of a lower and upper triangular matrix: $A=LU$.¹⁷

LU decomposition can be use to solve $Ax=b$ and calculate the determinant of $A$:

When $A$ is a symmetric positive definite matrix, Cholesky decomposition expresses $A$ as $A=R^TR$, where $R$ is a unique upper-triangular matrix with positive diagonal entries. Essentially, it is a LU decomposition with the property $L=U^T$.

Cholesky decomposition is useful in Monte Carlo simulation to generate correlated random variables as shown in the following problem:

How do you generate two $N(0,1)$ (standard normal distribution) random variables with correlation $\rho$ if you have a random number generator for standard normal distribution?

Solution: Two $N(0,1)$ random variables $x_1,\ x_2$ with a correlation $\rho$ can be generated from independent $N(0,1)$ random variables $z_1,\ z_2$ using the following equations:

It is easy to confirm that $\operatorname{var}(x_1)=\operatorname{var}(z_1)=1,\ \operatorname{var}(x_2)=\rho^2\operatorname{var}(z_1)+(1-\rho^2)\operatorname{var}(z_2)=1$, and $\operatorname{cov}(x_1,x_2)=\operatorname{cov}(z_1,\rho z_1+\sqrt{1-\rho^2}z_2)=\operatorname{cov}(z_1,\rho z_1)=\rho$.

This approach is a basic example using Cholesky decomposition to generate correlated random numbers. To generate correlated random variables that follow a $n$-dimensional 58 multivariate normal distribution $X=[X_1,X_2,\cdots,X_n]^T\sim N(\mu,\Sigma)$ with mean $\mu=[\mu_1,\mu_2,\cdots,\mu_n]^T$ and covariance matrix $\Sigma$ (a $n\times n$ positive definite matrix)¹⁸, we can decompose the covariance matrix $\Sigma$ into $R^TR$ and generate $n$ independent $N(0,1)$ random variables $z_1,\ z_2,\cdots,z_n$. Let vector $Z=[z_1,z_2,\cdots,z_n]^T$, then $X$ can be generated as $X=\mu+R^TZ$.¹⁹

Alternatively, $X$ can also be generated using another important matrix decomposition called singular value decomposition (SVD): For any $n\times p$ matrix $X$, there exists a factorization of the form $X=UDV^T$, where $U$ and $V$ are $n\times p$ and $p\times p$ orthogonal matrices, with columns of $U$ spanning the column space of $X$, and the columns of $V$ spanning the row space; $D$ is a $p\times p$ diagonal matrix called the singular values of $X$. For a positive definite covariance matrix, we have $V=U$ and $\Sigma=UDU^T$. Furthermore, $D$ is the diagonal matrix of eigenvalues $\lambda_1,\ \lambda_2,\cdots,\lambda_n$ and $U$ is the matrix of $n$ corresponding eigenvectors. Let $D^{1/2}$ be a diagonal matrix with diagonal elements $\sqrt{\lambda_1},\ \sqrt{\lambda_2},\ \cdots,\ \sqrt{\lambda_n}$, then it is clear that $D=(D^{1/2})^2=(D^{1/2})(D^{1/2})^T$ and $\Sigma=UD^{1/2}(UD^{1/2})^T$. Again, if we generate a vector of $n$ independent $N(0,1)$ random variables $Z=[z_1,z_2,\cdots,z_n]^T$, $X$ can be generated as $X=\mu+(UD^{1/2})Z$.