Linear Algebra Basics

$$ \begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix}^T = \begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix} $$

The lhs is a 1 x N row vector and rhs is a N x 1 column vector, tranpose from row vector to column vector is indicated by T.

Vector operations

Vector addition

$$ \begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix} + \begin{bmatrix}b_1&b_2&\cdots&b_n\end{bmatrix} = \begin{bmatrix}a_1+b_1&a_2+b_2&\cdots&a_n+b_n\end{bmatrix} $$

Vector multiplication

scale

$$ \begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix} \times a = \begin{bmatrix}ax_1&ax_2&\cdots&ax_n\end{bmatrix} $$

per-element multiplication

$$ \begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix} \times \begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix} = \begin{bmatrix}a_1x_1&a_2x_2&\cdots&a_nx_n\end{bmatrix} $$

dot product

$$ \begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix} \cdot \begin{bmatrix}a_1&a_2&\cdots&a_n\end{bmatrix} = \begin{bmatrix}x_1&x_2&\cdots&x_n\end{bmatrix} \begin{bmatrix}a_1\\a_2\\\cdots\\a_n\end{bmatrix} \\ = a_1x_1 + a_2x_2 + \cdots + a_nx_n $$

Matrix operations

Assume:

$$ M_a = \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nn}\\ \end{bmatrix} \\ M_b = \begin{bmatrix} b_{11}&b_{12}&\cdots&b_{1n}\\ b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ b_{n1}&b_{n2}&\cdots&b_{nn}\\ \end{bmatrix} \\ \\ v = \begin{bmatrix}v_1&v_2&\cdots&v_n\end{bmatrix} \\ $$

Matrix addition

$$ M_a + M_b = \begin{bmatrix} a_{11}+b_{11}&a_{12}+b_{12}&\cdots&a_{1n}+b_{1n}\\ a_{21}+b_{21}&a_{22}+b_{22}&\cdots&a_{2n}+b_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}+b_{n1}&a_{n2}+b_{n2}&\cdots&a_{nn}+b_{nn}\\ \end{bmatrix} $$

Matrix multiplication

$$ M_a \cdot v = M_a v^T = \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nn}\\ \end{bmatrix} \begin{bmatrix} v_1\\v_2\\\cdots\\v_n\\ \end{bmatrix} = \begin{bmatrix} a_{11}v_1 + a_{12}v_2 + \cdots + a_{1n}v_n\\ a_{21}v_1 + a_{22}v_2 + \cdots + a_{2n}v_n\\ \vdots\\ a_{n1}v_1 + a_{n2}v_2 + \cdots + a_{nn}v_n\\ \end{bmatrix} $$

$$ M_a \cdot M_b = M_a M_b^T = \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nn}\\ \end{bmatrix} \begin{bmatrix} b_{11}&b_{12}&\cdots&b_{1n}\\ b_{21}&b_{22}&\cdots&b_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ b_{n1}&b_{n2}&\cdots&b_{nn}\\ \end{bmatrix} ^ T \\ = \begin{bmatrix} a_{11}b_{11}+a_{12}b_{12}+\cdots+a_{1n}b_{1n}& a_{11}b_{21}+a_{12}b_{22}+\cdots+a_{1n}b_{2n}& \cdots& a_{11}b_{n1}+a_{12}b_{n2}+\cdots+a_{1n}b_{nn}\\

a_{21}b_{11}+a_{22}b_{12}+\cdots+a_{2n}b_{1n}& a_{21}b_{21}+a_{22}b_{22}+\cdots+a_{2n}b_{2n}& \cdots& a_{21}b_{n1}+a_{22}b_{n2}+\cdots+a_{2n}b_{nn}\

\vdots&\vdots&\ddots&\vdots\

a_{n1}b_{11}+a_{n2}b_{12}+\cdots+a_{nn}b_{1n}& a_{n1}b_{21}+a_{n2}b_{22}+\cdots+a_{nn}b_{2n}& \cdots& a_{n1}b_{n1}+a_{n2}b_{n2}+\cdots+a_{nn}b_{nn}\ \end{bmatrix} $$

C++ Implementation

Implement Vector & Matrix data structure

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// N x N matrix
template <typename TYPE, size_t N> struct Matrix {
    // 1 x N row vector, transpose as operator need
    struct Vector {
        TYPE mEntries[N];
        TYPE& operator[](size_t index) { return mEntries[index]; }
        const TYPE& operator[](size_t index) const { return mEntries[index]; }
        
        ...
    };
    
    Vector mEntries[N];     // matrix row vectors
    Vector& operator[](size_t index) { return mEntries[index]; }
    const Vector& operator[](size_t index) const { return mEntries[index]; }
    
    Matrix& transpose() { ... }
    
    ...
};

Implement Vector operators

Implement vector addition

$$ V_{lhs} + V_{rhs} $$

1
2
3
4
5
Vector operator+(const Vector& rhs) const {
    Vector result;
    for (size_t i = 0; i < N; ++i) result[i] = mEntries[i] + rhs[i];
    return result;
}

Implement vector dot product

$$ V_{lhs} \cdot V_{rhs} = V_{lhs} V_{rhs}^T $$

1
2
3
4
5
TYPE operator*(const Vector& rhs) const {
    TYPE result;
    for (size_t i = 0; i < N; ++i) result += mEntries[i] + rhs[i];
    return result;
}

Implement Matrix operators

Implement matrix addition

$$ M_{lhs} + M_{rhs} $$

1
2
3
4
5
6
Matrix operator+(const Matrix& rhs) const {
    Matrix result;
    for (size_t i = 0; i < N; ++i)
        result[i] = mEntries[i] + rhs[i];
    return result;
}

Implement matrix dot product

$$ M_{lhs} \cdot V_{rhs} = M_{lhs} V_{rhs}^T $$

1
2
3
4
5
6
Vector operator*(const Vector& rhs) const {
    Vector result;
    for (size_t i = 0; i < N; ++i)
        result[i] = mEntries[i] * rhs;
    return result;
}

$$ M_{lhs} \cdot M_{rhs} = M_{lhs} M_{rhs}^T $$

1
2
3
4
5
6
7
Matrix operator*(const Matrix& rhs) const {
    Matrix result;
    for (size_t i = 0; i < N; ++i)          // row
        for (size_t j = 0; j < N; ++j)      // column
            result[i][j] = mEntries[i] * rhs[j];
    return result;
}