<jupyter_start><jupyter_text>05 Linear Independence  First two elements of a basis of the space of images.  Unit 1: Vectors, Book ILA Ch. 1-5- 01 Vectors- 02 Linear Functions- 03 Norms and Distances- 04 Clustering- **_05 Linear Independence_** Unit 2: Matrices, Book ILA Ch. 6-11 + Book IMC Ch. 2 Unit 3: Least Squares, Book ILA Ch. 12-14 + Book IMC Ch. 8 Unit 4: Eigen-decomposition, Book IMC Ch. 10, 12, 19  Outline: 05 Linear Independence- **[Linear Independence](sec-linear)**- [Basis](Basis)- [Orthonormal Vectors](Orthonormal)  Linear Dependence$\color{EF5645}{\text{Definition}}$: A set of $n$-vectors ${a_1, . . . , a_k}$ (with $k ≥ 1$) is linearly dependent if:$$β_1a_1 + · · · + β_ka_k = 0$$**holds for some $β_1, . . . , β_k$ that are not all zero**. This statement is equivalent to: at least one $a_i$ is a linear combination of the others.- ${a_1}$ is linearly dependent only if $a_1 = 0$.- ${a_1, a_2}$ is linearly dependent only if one $a_i$ is multiple of the other.- for $k > 2$, there is no simple way to state condition. $\color{047C91}{\text{Exercise}}$: Which sets of vectors are linearly dependent? $\color{047C91}{\text{Example}}$: The following vectors:$$a_1 = \begin{pmatrix}    0.2 \\    -7 \\    8.6 \end{pmatrix}, \quad a_2 = \begin{pmatrix}    -0.1 \\    2 \\    -1\end{pmatrix} \quad a_3 = \begin{pmatrix}    0 \\    -1 \\    2.2\end{pmatrix}$$are linearly dependent because:- $a_1 + 2a_2 − 3a_3 = 0$,- we can express any of them as linear combination of the other two, e.g., $a_2 = (−1/2)a_1 + (3/2)a_3$  Linear Independence$\color{EF5645}{\text{Definition}}$: The set of $n$-vectors ${a_1, . . . , a_k}$ (with $k ≥ 1$) is linearly independent if it is not linearly dependent, i.e. if $$β_1a_1 + · · · + β_ka_k = 0$$**holds only when** $β_1 = · · · = β_k = 0$. This statement is equivalent to: no $a_i$ is a linear combination of the others.$\color{047C91}{\text{Example}}$: The one-hot $n$-vectors $e_1, . . . , e_n$ are linearly independent.  Property of linear independence$\color{6D7D33}{\text{Property}}$: Take linearly independent vectors $a_1, . . . , a_k$. Suppose $x$ is linear combination of the $a_1, . . . , a_k$: $$x = β_1a_1 + · · · + β_ka_k.$$Then, the coefficients $\beta_1, ..., \beta_k$ are unique.$\color{EF5645}{\text{Remark}}$: This means that, in principle, we can compute the coefficients from $x$.  Linear (in)dependence & dimension$\color{6D7D33}{\text{Propositions}}$:- A linearly independent set of $n$-vectors $a_1, . . . , a_k$ can have at most $n$ elements, i.e. $k \leq n$.- Any set of $n + 1$ or more $n$-vectors is linearly dependent.$\color{047C91}{\text{Exercise}}$: Are the vectors $(1, 2), (2, 3)$ and $(3, 0)$ linearly dependent or independent?   Outline: 05 Linear Independence- [Linear Independence](sec-linear)- **[Basis](Basis)**- [Orthonormal Vectors](Orthonormal)  Basis$\color{EF5645}{\text{Definition}}$: A set of $n$ linearly independent $n$-vectors $a_1, . . . , a_n$ is called a basis of the space of $n$-vectors.$\color{047C91}{\text{Example}}$: The set of $n$ one-hot $n$-vectors is a basis of the space of $n$-vectors. This is why we can also call them "basis vectors".$\color{047C91}{\text{Example}}$: What is a possible basis:- For the space of colors represented as vectors $(r, g, b)$? - For the space of documents with dictionary $D$? - For the space of $8\times8$ images? - Space of colors as $3$-vectors: $(r, g, b)$    - A basis:  set of vectors representing red, green and blue.- Space of documents as $n$-vectors on a dictionary of $n$ words    - A basis: set of vectors representing on dictionary word each.- Space of 8x8 images as $64$-vectors    - A basis: set of images with only one black pixel.    Properties of a basis$\color{6D7D33}{\text{Properties}}$: If $a_1, . . . , a_n$ is a basis of the space of $n$-vectors, then:- Any $n$-vector $b$:  - can be expressed as a linear combination of them: $b = β_1a_1 + · · · + β_n a_n$ for some $β_1, . . . , β_n$.  - and the coefficients $β_1, . . . , β_n$ are unique.    $\color{EF5645}{\text{Definition}}$: The formula above is called expansion of $b$ in the $a_1, . . . , a_n$ basis.  $\color{047C91}{\text{Example}}$: Compute expansion of $b = (b_1, ..., b_n)$ in basis $e_1, ..., e_n$  Outline: 05 Linear Independence- [Linear Independence](sec-linear)- [Basis](Basis)- **[Orthonormal Vectors](Orthonormal)**  Orthogonal, Normalized, Orthonormal$\color{EF5645}{\text{Definitions}}$: The $n$-vectors $a_1, . . . , a_k$ are:- (mutually) orthogonal if $a_i ⊥ a_j$ for all $i , j$- normalized if $‖a_i ‖ = 1$ for $i = 1, . . . , k$- orthonormal if they are orthogonal and normalized.$\color{047C91}{\text{Example}}$: Give examples of orthogonal, normalized and orthonormal vectors in 2D. Draw them.  Properties of Orthonormal Vectors$\color{6D7D33}{\text{Properties}}$: If $a_1, ..., a_k$ are orthonormal, then:- $a_i^Ta_j = 0$ if $i\neq j$ and $a_i^Ta_i = 1$,- $k\leq n$,- $a_1, ..., a_k$ are linearly independent.$\color{EF5645}{\text{Definition}}$: A set of $n$ orthonormal $n$-vectors is called an orthonormal basis.  Examples of Orthonormal Basis$\color{047C91}{\text{Examples}}$:- One-hot $n$-vectors: $e_1, ...., e_n$- The $3$-vectors: $$a_1 = \begin{pmatrix}    0 \\    0 \\    -1 \end{pmatrix}, \quad a_2 = \begin{pmatrix}    1 / \sqrt{2} \\    1 / \sqrt{2} \\    0\end{pmatrix} \quad a_3 = \begin{pmatrix}    1 / \sqrt{2} \\    -1 / \sqrt{2} \\    0\end{pmatrix}$$$\color{047C91}{\text{Exercise}}$: Show that the $3$-vectors above form an orthonormal basis using math computations. $\color{047C91}{\text{Exercise}}$: Show that these form an orthonormal basis using Python: $$a_1 = \begin{pmatrix}    0 \\    0 \\    -1 \end{pmatrix}, \quad a_2 = \begin{pmatrix}    1 / \sqrt{2} \\    1 / \sqrt{2} \\    0\end{pmatrix} \quad a_3 = \begin{pmatrix}    1 / \sqrt{2} \\    -1 / \sqrt{2} \\    0\end{pmatrix}$$<jupyter_code>a1 = np.array([0, 0, 1]); a2 = np.array([1/np.sqrt(2), 1/np.sqrt(2), 0])

print(np.inner(a1, a2)) # Do same for a1, a3 and a2, a3

np.linalg.norm(a1) # Do same for a2 and a3<jupyter_output>0.0
{'fraction_non_alphanumeric': 0.1733179419525066, 'fraction_numerical': 0.04617414248021108, 'mean_word_length': 3.5430711610486894, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '651684', 'license': 'MIT', 'n_tokens_mistral': 2324, 'n_tokens_neox': 2105, 'n_words': 756, 'path': 'lectures/lec05_linear_independence.ipynb', 'repo_name': 'bioshape-lab/ucsb-ece-3', 'size': '6064'}