> For the complete documentation index, see [llms.txt](https://ztlevi.gitbook.io/ml-101/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ztlevi.gitbook.io/ml-101/ml-fundamentals/linear_algebra.md).

# Linear Algebra

## The Rank of a Matrix

You can think of an $$r \times c$$ matrix as a set of $$r$$ row [vectors](https://stattrek.com/help/glossary.aspx?Target=Vectors), each having $$c$$ elements; or you can think of it as a set of $$c$$ column vectors, each having $$r$$ elements.

The **rank** of a matrix is defined as (a) the maximum number of [linearly independent](https://stattrek.com/help/glossary.aspx?Target=Linear_dependence_of_vectors) *column* vectors in the matrix or (b) the maximum number of linearly independent $$row$$ vectors in the matrix. Both definitions are equivalent.

For an $$r \times c$$ matrix,

* If $$r$$ is less than $$c$$, then the maximum rank of the matrix is $$r$$.
* If $$r$$ is greater than $$c$$, then the maximum rank of the matrix is $$c$$.

The rank of a matrix would be zero only if the matrix had no elements. If a matrix had even one element, its minimum rank would be one.

For example, the following matrix has rank of 2.

$$
X = \begin{pmatrix} 1 & 2 & 4 & 4 \ 3 & 4 & 8 & 0 \end{pmatrix}
$$

## [Singular Value Decomposition](https://www.youtube.com/watch?v=P5mlg91as1c)

### Formula

$$A\_{\[m \times n]}=U\_{\[m \times r]} \Sigma\_{\[r \times r]} (V\_{\[n \times r]})^T$$

* A: Input data matrix
  * $$m \times n$$ matrix (e.g. m documents, n terms)
* U: left singular vectors
  * $$m \times r$$ matrix (m documents, r concepts)
* $$\Sigma$$: Singular values
  * $$r \times r$$ diagonal matrix (strength of each `concept`) (r: rank of matrix A)
* V: Right singular vectors
  * $$n \times r$$ matrix (n terms, r concepts)

![](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-217c926d96d298944faa78e99c86d0a9b0fdd52d%2Fsvd_1.jpg?alt=media)

### Properties

It is always possible to decompose a real matrix A into $$A=U \Sigma V^T$$, where

* $$U, \Sigma, V$$: unique
* $$U, V$$: column orthonormal
  * $$U^T U = I$$; $$V^T V = I$$ (I: identity matrix)
  * (Columns are orthogonal unit vectors)
* $$\Sigma$$: diagonal
  * Entries (singular values) are positive, and sorted in decreasing order ($$\sigma\_1 \geq \sigma\_2 \geq \cdots \geq 0$$)

![](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-25f3ea87dace0f1d7b6f40a57cd95e8ad779d937%2Fsvd_2.jpg?alt=media)

![](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-118e1bb76afc2eacf6913bcda6d194bfd4b6c7d7%2Fsvd_3.jpg?alt=media)

![](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-bd40dc54a0efee40506b45b1ab94c19099f66aac%2Fsvd_4.jpg?alt=media)

![](https://637078585-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MYsi-h_n0zY_8MKKgyu%2Fuploads%2Fgit-blob-1fd2d3d85ca37fac896cdac0d977da91f337d04f%2Fsvd_5.jpg?alt=media)

### Interpretation

* U: user-to-concept similarity matrix
* V: movie-to-concept similarity matrix
* $$\Sigma$$: its diagonal elements `strength` of each concept