The computational time required to compute products between matrices varies significantly depending on the type of operation. Elementwise operations, such as the Hadamard product, are relatively fast and can be computed in quadratic time. In contrast, standard matrix-matrix multiplication is considerably more computationally intensive, generally requiring cubic time to execute.

Computational Complexity of Matrix Products

Matrices can be multiplied, with each value in the resulting matrix defined by the function
$C_{i,j} = \sum_k A_{i,k} B_{k,j}$

The size of the matrix is found by the height of the first node and the width of the second node. 

Michigan State University

University of Michigan - Ann Arbor

The linear algebra necessary to further explain Machine Learning in our capacity, requires a basic understanding of 
- Linear Systems of Equations
- Linear Transformations
- Vector Spaces
- Orthogonality
- Eigenvalues


Linear Algebra

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

Bretscher, O. (2019). Linear algebra with applications. Upper Saddle River, NJ: Pearson Education, Inc.

[Link to GitHub repo](https://github.com/gomson/Linear-Algebra/blob/master/Linear%20Algebra%20with%20Applications%205th%20Edition%20Otto%20Bretsch%20.pdf) 

Linear Algebra with Applications

Matrix is a two dimensional arrangement of numbers.

Linear Algebra - Matrices

To get the transpose of a matrix, we should do a mirror symmetry operation on the matrix according to one of its specific diagonal line, called the main diagonal.  The gotten matrix should be denoted as $A^T$.

Transpose

Matrix Multiplication

Used similarly to an inverse, but for nonsquare matrices. Can find rough values for systems with no real solution. Often denoted as $A^\dagger$ or "A dagger".

Given $A$ is an $m x n$ matrix and $A \vec{x} = \vec{y}$, the pseudoinverse of $A$ is the matrix $B$ such that $\vec{x} = B \vec{y}$.

Formal Definition: $A^\dagger = \lim_{\alpha \to 0} (A^T A + \alpha I )^{-1} A^T$
Practical Formula: $A^\dagger = V D^\dagger U^T$, where $U, D,$ and $V$ are the singular value decomposition of A, and the pseudoinverse, $D^\dagger$ of a diagonal matrix, $D$, is found by taking the reciprocal of its nonzero elements, then taking the transpose of the resulting elements.

Moore-Penrose Pseudoinverse

timeparticle. (2009, April 8). Using the Moore-Penrose Pseudoinverse to Solve Linear Equations [Video]. YouTube. https://youtu.be/5bxsxM2UTb4

Using the Moore-Penrose Pseudoinverse to Solve Linear Equations

The trace of a matrix is the sum of all values along its main diagonal, denoted $tr(A)$, where $A$ is an $m x m$ matrix. This may only be used for square matrices.

Traces have various properties:
$tr(A) = tr(A^T)$
$tr(ABC) = tr(CAB) = tr(BCA)$
For $A \in \mathbb{R}^{m x n} and B \in \mathbb{R}^{n x m}$, $tr(AB) = tr(BA)$. 

Example:
$tr(\begin{bmatrix} 2 & 8 & 3\\ 1 & 4 & 6\\ 7 & 9 & 5 \end{bmatrix}) = 2 + 4 + 5 = 11$

Linear Algebra (Trace)

The determinant of a matrix, $A$, is the product of $A$'s eigenvalues, where $A$ is an $m x m$ matrix. It has numerous applications in finding volume and using integrals. It can only be used on square matrices.

Determinants of different sizes:
$det(\begin{bmatrix} a \end{bmatrix}) = a$
$det(\begin{bmatrix} a & b\\ c & d \end{bmatrix}) = ad-bc$
$det(\begin{bmatrix} a & b & c\\ d & e & f\\ g & h & i \end{bmatrix}) = a(ei-fh) - b(di-fg) + c(dh-eg)$

Linear Algebra (Determinant)

A matrix satisfying that have nonzero entries only along the main diagonal is called diagonal matrix. Formally, a matrix $D$ is a diagonal matrix if and only if $D_{i,j} = 0$ for all $i \neq j$.
$diag(v)$ is used to denote a diagonal matrix which main diagonal is the vector $v$.
Keep in mind that not all diagonal matrices need to be square.

Linear Algebra - Diagonal Matrices

A vector with unit norm is called a unit vector.

Linear Algebra - Unit Vector

Vector $x$ and $y$ are orthogonal means that $x^Ty=0$

Linear Algebra - orthogonal

If the vectors are not only orthogonal but also unit vectors, we call them orthonormal.

Linear Algebra - orthonormal

A matrix is orthonormal matrix if and only if its rows are mutually orthonormal and its columns are mutually orthonormal as well.

Linear Algebra - orthogonal matrix

A vector $v$ is an eigenvector of a square matrix $A$ if and only if it's a nonzero vector which  multiplication by $A$ alters only the scale of $v$:
$Av = \lambda v$

Linear Algebra - eigenvector

Eigenvalue is the value $\lambda$ corresponding to the eigenvector which satisfies 
$Av = \lambda v$

Linear Algebra - eigenvalue

Suppose that a matrix A has n linearly independent eigenvectors {$v^{(1)}$, . . . , $v^{(n)}$} with corresponding eigenvalues {$\lambda _1$, . . . , $\lambda _n$}. We may concatenate all the eigenvectors to form a matrix V with one eigenvector per column: V = [$v^{(1)}$ , . . . , $v^{(n)}$]. Similarly, we can get a vector containing eigenvalues, naming it as $\lambda$. The eigendecomposition of A is then given by
$A = Vdiag(\lambda)V^{-1}$

Linear Algebra - eigendecomposition

Singular value decomposition (SVD) is an unsupervised dimensionality reduction technique used for feature extraction.  The singular value decomposition of an m x n matrix M is a factorization of the form U$$\sum$$M*.  U is an m x m unitary matrix. $$\sum$$ is a m x n diagonal matrix. V is a v x v unitary matrix.
Image link: [www.wikiwand.com/en/Singular_value_decomposition](https://www.wikiwand.com/en/Singular_value_decomposition)
 

Singular value decomposition (SVD)

The dot product can be conducted between two matrices if they have the same dimension. The dot product C=AB can be computed as $C_{i,j} =A_{i,:}B_{:,j}$.
Multiplication rules:
A(B+C)=AB+AC
A(BC)=(AB)C

Linear Algebra - Dot Product and Multiplication Rules

An n-dimensional identity matrix $I_{n}$ is a matrix that has ones on the diagonal and zeros as the rest of the elements.
The inverse of a matrix A can be defined as $A^{-1}$ such that $A^{-1}$A=$I_{n}$
We can use matrix inverse to solve a $Ax=B$: $x=BA^{-1}$

Linear Algebra - Identity and Inverse Matrices

A linear combination of a set of vectors {$V_{1}$,$V_{2}$,,...,$V_{n}$} is defined as $\sum_{i}$ $c_{i}V_{i}$ where $c_{i}$ are coefficents.
The span of a set of vectors is all the vectors that could be obtained through its linear combination.
A set of vectors is linearly independent if no vector is a linear combination of the other vectors in the set.

Linear dependence and span

In machine learning, we use norm to measure the size of a vector. An $L^{p}$ norm is defined as $||x||_{p}$=($\sum_{i}$ $|x_{i}|^{p}$)$^{1/p}$
Common norms such as L1 and L2 norm can be obtained by substituting p=1 and p=2 into the above formula. There are also some other norms such as max norm:
$||x||$=max$_{i}$ $|x_{i}|$

Linear Algebra - Norm

A standard basis vector, often denoted as $\vec{e}_k$, is a vector within a given vector space that has a value of 1 in its k-th coordinate and 0 in all other coordinates. These vectors form a basis, meaning any vector in the space can be represented as a linear combination of them.

Standard Basis Vector

The notation `a = (a, ..., a, a)` is used to represent a tuple or vector where every element is identical. This format signifies an ordered sequence composed entirely of the same element, in this case 'a', enclosed in parentheses.

Notation for a Tuple of Identical Elements

The memory state, denoted as Mem, is represented as a tuple. The first element of the tuple is the arithmetic mean of key vectors ($\mathbf{k}_j$) and the second element is the arithmetic mean of value vectors ($\mathbf{v}_j$), both summed from index $j=0$ to $i$. The formula is: $$Mem = \left( \frac{\sum_{j=0}^{i} \mathbf{k}_j}{i + 1}, \frac{\sum_{j=0}^{i} \mathbf{v}_j}{i + 1} \right)$$ This calculation effectively summarizes the information contained in the sequence of key-value pairs up to step $i$.

Memory State as an Average of Keys and Values

A sequence of variables is commonly denoted as $x = (x_1, x_2, \dots, x_n)$ or simply $x_1, x_2, \dots, x_n$. This represents an ordered collection of elements, where each variable $x_i$ is identified by its index $i$. Unlike a set, the order of elements in a sequence is significant, making it a foundational structure for representing data like time series, text, or the components of a vector.

Notation for a Sequence of Variables

A tensor is a generic mathematical framework for describing multidimensional arrays of numerical values, extending the concept of vectors and matrices to an arbitrary number of axes. The specific terminology depends on the number of axes: a one-dimensional tensor is a vector, a two-dimensional tensor is a matrix, and a tensor with $$n > 2$$ axes is referred to as an $$n^{	extrm{th}}$$-order tensor. Each individual scalar value within the tensor is called an element.

Tensor

A matrix is a rectangular array of numbers logically arranged in horizontal rows and vertical columns. In the context of multidimensional data arrays, a matrix is formally defined as a $$2^{\textrm{nd}}$$-order tensor, meaning it is a tensor with exactly two axes. It provides a structured mathematical format to compactly organize data and is frequently used to represent systems of linear equations.

Matrix

An element-wise product (also known as the Hadamard product) of two matrices with the same shape, such as $$A_{m,n}$$ and $$B_{m,n}$$, results in a new matrix of identical shape. Each element in the resulting matrix is the product of the elements at the corresponding positions in matrices $$A$$ and $$B$$. This is a specific instance of a binary elementwise tensor operation.

Element-wise Product

When performing elementwise binary operations on two tensors that do not share the same shape, deep learning frameworks utilize a broadcasting mechanism to make their dimensions compatible. This procedure involves two sequential steps: first, it expands one or both tensors by replicating their elements along any axis with a length of $$1$$ so that both tensors acquire identical shapes. Second, the framework executes the desired elementwise operation on these newly expanded, uniformly shaped tensors.

Broadcasting Mechanism

A vector can be conceptualized as a fixed-length array of scalars. Mathematically and computationally, vectors are implemented as $$1^{	extrm{st}}$$-order tensors. When vectors represent data from real-world datasets, their scalar values hold real-world significance, such as a vector representing a patient where its components correspond to specific vital signs.

Vector

Most everyday mathematics consists of manipulating numbers one at a time. Formally, these single numerical values are called scalars. For example, in the expression for converting temperature, $$c = \frac{5}{9}(f - 32)$$, the values $$5$$, $$9$$, and $$32$$ are constant scalars, whereas the variables $$c$$ and $$f$$ represent unknown scalars.

Scalars

A symmetric matrix is a specific subset of square matrices that are perfectly equal to their own transpose. Mathematically, a square matrix $$\mathbf{A}$$ is considered symmetric if and only if the condition $$\mathbf{A} = \mathbf{A}^	op$$ holds true. This implies that the matrix elements are mirror images across the main diagonal, meaning that $$a_{ij} = a_{ji}$$ for all valid row indices $$i$$ and column indices $$j$$.

Learn Before

Related

Learn After