**Definition**A finite set of nonzero vectors $\{x_1, \ldots, x_p \}$ is called*linear dependent*, if there exist scalars $c_1, \ldots, c_p$ not all zero such that $$ \sum\limits_{i=1}^p c_i x_i = 0. $$**Definition**A*rank*of a matrix $A$ is a number of linear independent columns**Definition**A matrix $A$ is called*positive-definite*, if for any nonzero vector $x$ the scalar $x^{\top}A x$ is positive: $$ A \succ 0 \iff x^{\top}A x > 0 $$ In the same way, one can define negative-definite matrix and positive/negatve semidefinite matrix.

**Definition**Square real matrix is called*orthogonal*if $$ AA^{\top} = I $$**Definition**A trace of square matrix $A$ is a sum of its diagonal elements: $$ \mathrm{trace}(A) = \sum_{i=1}^n a_{ii} $$

- Matrix by vector product:
$$
(Ax)_i = \sum_{k=1}^n a_{ik}x_k,
$$
where $A \in \mathbb{R}^{m \times n}$ and $x \in \mathbb{R}^n$:
- for dense matrix $A$ — $O(mn)$
- for sparse matrix $A$ where $N \ll mn$ nonzero elements — $O(N)$
- for lowrank matrix $A = UV^{\top}$, where $U \in \mathbb{R}^{m \times p}, \; V \in \mathbb{R}^{n \times p}$ and $p \ll \min(n, m)$ — $O(p(n + m))$
- for some special matrices (Toeplitz matrix, circulant, $\mathcal{H}$ and $\mathcal{H}^2$ matrices) multiplication by vector can be performed faster

- Matrix by matrix multiplication:
$$
A = BC \qquad a_{ij} = \sum_{k=1}^p b_{ik}c_{kj},
$$
where $A \in \mathbb{R}^{m \times n}$, $B \in \mathbb{R}^{m \times p}$ и $C \in \mathbb{R}^{p \times n}$
- for dense matrices $B$ and $C$ — $O(mnp)$ operations
- significantly faster if one or both matrices $B$ and $C$ are sparse

- Diagonal matrices $A$ — $O(n)$ operations
- Lower- and uppertriangular matrices — $O(n^2)$ operations. The methods to solve such systems is called forward and backward substitutions respectively
- Orthogonal matrices $A$
- for arbitrary orthogomal matrix — $O(n^2)$ operations
- if one knows structure if the orthogonal matrix (for example $A = I - 2uu^{\top}$, $u$ is a vector) — $O(n)$ operations

**Q:** What geometrically means multiplication matrix $A = I - 2uu^{\top}$ by any vector $x$?

- Represent matrix $A$ as product of $k$ "simple" matrices (diagonal, lower- and uppertriangular, and others...) $$ A = A_1A_2\ldots A_k $$
- To get $x$ solve $k$ systems of linear equations $$ A_1x_1 = b \quad A_2x_2 = x_1 \quad \ldots \quad A_kx = x_{k-1} $$ This can be done fast since matrices $A_i$ are "simple".

This method is appropriate to solve a $m$ systems of linear equations with constant matrix $A$ and different right-hand side $b_i, \; i=1,\ldots,m$:

- Matrix $A$ factorization in product of simple matrices is performed only once
- After that one can solve $m$ systems of linear equations for every right-hand side $b_i$

**Theorem.** Any nonsingular matrix $A$ can be represented in the following form
$$
A = PLU,
$$
where $P$ is a permutation matrix, $L$ is lowertriangular matrix and $U$ is uppertriangular matrix

LU factorization requires $2n^3/3$ operations

**Q:** What is complexity of solving system of linear equations $Ax=b$ given LU factorization of matrix $A$?

**Q:** Why do we need permutation matrix $P$?

**Theorem.** Any symmetrix and positive definite matrix $A$ can be represebted in the following form
$$
A = LL^{\top},
$$
where $L$ is a lowertriangulat matrix.

Cholesky factorization requires $n^3/3$ operations.

**Q:** What is complexity of solving system of linear equations $Ax=b$ given Cholesky factorization of matrix $A$?

**Definition.** Nonzero vector $x$ is called *eigenvector* of a transformation given by matrix $A$ if
$$
Ax = \lambda x,
$$
where $\lambda$ is eigenvalue corresponding to the eigenvector $x$.

If matrix $A$ has $n$ linear independent eigenvector, then it can be represented in the form of *spectral decomposition*:
$$
A = X\Lambda X^{-1},
$$
where $\Lambda = \mathrm{diag}(\lambda_1, \ldots, \lambda_n)$, and $X = [x_1, \ldots, x_n]$.

- Complexity of computing all eigenvectors and eigenvalues is $O(n^3)$ - Jacobi eigenvalue algorithm, QR-algorithm, using Schur decomposition...
- But full spectral decomposition is rarely needed.
Usually only some leading eigenvalues-eigenvectors are required.
To solve this problem, one can use
*power method*and*inverse iteration method*