03 Linear Independence, Basis, SLE, Eigen-staff

image.png լուսանկարի հղումը, Գազանանոց, Հեղինակ՝ Elmira Gokoryan

📚 Նյութը ToDo

🏡 Տնային

Note
  1. ❗❗❗ DON’T CHECK THE SOLUTIONS BEFORE TRYING TO DO THE HOMEWORK BY YOURSELF❗❗❗
  2. Please don’t hesitate to ask questions, never forget about the 🍊karalyok🍊 principle!
  3. The harder the problem is, the more 🧀cheeses🧀 it has.
  4. Problems with 🎁 are just extra bonuses. It would be good to try to solve them, but also it’s not the highest priority task.
  5. If the problem involve many boring calculations, feel free to skip them - important part is understanding the concepts.
  6. Submit your solutions here (even if it’s unfinished)

Systems of Linear Equations

01: GPS positioning - from 2D to 3D

GPS systems solve systems of equations to determine location. Understanding this process helps grasp how linear systems work in practice and why we need the right number of equations.

Part A: 2D Positioning (Easier warm-up)

Imagine you’re lost in a 2D world and receive distance signals from cell towers: - Tower A at (0, 0): You are 5 units away - Tower B at (6, 0): You are 3 units away

  1. Write the system of equations for your position (x, y).
  2. Solve it step by step using substitution or elimination.
  3. Plot the circles and find their intersection point(s).

Part B: 3D GPS Challenge

Now for real GPS with 4 satellites in 3D space: - Why do you need exactly 4 satellites for 3D positioning when you only need 2 towers for 2D? - What happens if you only have 3 satellites?

02: Linear regression with normal equations

The normal equation provides a direct way to solve linear regression problems, connecting linear algebra to machine learning prediction tasks.

You have the following data points for house size (x) vs price (y): - (50, 100), (100, 180), (150, 280)

  1. Set up the design matrix X (including the intercept column) and target vector y.
  2. Solve the normal equation \(\vec{\theta} = (X^T X)^{-1} X^T \vec{y}\) (set up the system of linear equations and you can use Gaussian elimination).
  3. Find the line equation \(y = \theta_0 + \theta_1 x\).
  4. Plot the data points and your fitted line.
  5. Predict the price for a 120 square meter house.

Hint for 1.: We want to express calculating y (the price) as a matrix multiplication of X and theta.

\[\vec{y} = X \vec{\theta}\]

Where \(\vec{\theta} = \begin{pmatrix} \theta_0 \\ \theta_1 \end{pmatrix}\). In order for each \(y_i = \theta_0 + \theta_1 x_i\), we set up the design matrix (X) as follows: \[X = \begin{pmatrix} 1 & 50 \\ 1 & 100 \\ 1 & 150 \end{pmatrix}\]

Calculate the product \(X \vec{\theta}\) to verify that each \(y_i\) corresponds to plugging in \(x_i\) into the line equation.

Step 1: Set up the design matrix X and target vector y

For the data points (50, 100), (100, 180), (150, 280), we need to include an intercept column:

\[X = \begin{pmatrix} 1 & 50 \\ 1 & 100 \\ 1 & 150 \end{pmatrix}, \quad \vec{y} = \begin{pmatrix} 100 \\ 180 \\ 280 \end{pmatrix}\]

Step 2: Solve the normal equation

First, compute \(X^T X\): \[X^T = \begin{pmatrix} 1 & 1 & 1 \\ 50 & 100 & 150 \end{pmatrix}\]

\[X^T X = \begin{pmatrix} 1 & 1 & 1 \\ 50 & 100 & 150 \end{pmatrix} \begin{pmatrix} 1 & 50 \\ 1 & 100 \\ 1 & 150 \end{pmatrix} = \begin{pmatrix} 3 & 300 \\ 300 & 35000 \end{pmatrix}\]

Next, compute \(X^T \vec{y}\): \[X^T \vec{y} = \begin{pmatrix} 1 & 1 & 1 \\ 50 & 100 & 150 \end{pmatrix} \begin{pmatrix} 100 \\ 180 \\ 280 \end{pmatrix} = \begin{pmatrix} 560 \\ 59000 \end{pmatrix}\]

Now solve \((X^T X) \vec{\theta} = X^T \vec{y}\): \[\begin{pmatrix} 3 & 300 \\ 300 & 35000 \end{pmatrix} \begin{pmatrix} \theta_0 \\ \theta_1 \end{pmatrix} = \begin{pmatrix} 560 \\ 59000 \end{pmatrix}\]

Using Gaussian elimination: - From the first equation: \(3\theta_0 + 300\theta_1 = 560\) - From the second equation: \(300\theta_0 + 35000\theta_1 = 59000\)

Multiply the first equation by 100: \(300\theta_0 + 30000\theta_1 = 56000\)

Subtract from the second equation: \(5000\theta_1 = 3000\), so \(\theta_1 = 0.6\)

Substitute back: \(3\theta_0 + 300(0.6) = 560\), so \(3\theta_0 = 380\), giving \(\theta_0 = 126.67\)

Step 3: Line equation \[y = 126.67 + 0.6x\]

Step 4: Verification Check our solution with the data points: - For x = 50: \(y = 126.67 + 0.6(50) = 156.67\) (close to 100) - For x = 100: \(y = 126.67 + 0.6(100) = 186.67\) (close to 180) - For x = 150: \(y = 126.67 + 0.6(150) = 216.67\) (close to 280)

Step 5: Prediction for 120 square meters \[y = 126.67 + 0.6(120) = 198.67\]

The predicted price for a 120 square meter house is approximately 198.67 (thousand units).

03: The cheese shop multicollinearity problem

Real datasets often contain redundant features that are linear combinations of each other, causing problems in machine learning models.

A cheese shop tracks the following features for each cheese: - Price in AMD: \(p_1\) - Price in USD: \(p_2\) - Weight in kilograms: \(w_1\) - Weight in pounds: \(w_2\)

Given the conversion rates: 1 USD = 400 AMD and 1 kg = 2.2 pounds.

  1. Linear dependence detection: Which features are linearly dependent? Write the exact relationships.

  2. Matrix rank problem: If you create a data matrix with these 4 features for 100 cheeses, what would be the maximum possible rank? Why?

  3. Feature selection: Which 2 features should you keep to avoid multicollinearity? Explain your choice.

  4. System solvability: If you try to fit a model using all 4 features, what problems might arise? Hint: Think about the normal equation and matrix invertibility.

04: System consistency analysis

For which values of \(a\) does the following system have 0, 1, or infinitely many solutions?

\[\begin{cases} x + 2y + z = 1 \\ 2x + 4y + az = 2 \\ -x - y + (a-1)z = 0 \end{cases}\]

05: Linear independence in polynomial space

Determine if the set \(\{1 + t, 1 + 2t, 1 + t + t^2\} \subset P_2\) is linearly independent. If dependent, express one polynomial as a linear combination of the others.

06: Matrix subspaces and trace

Let \(V = \{M \in M_{2 \times 2} : \text{tr}(M) = 0\}\) be the set of \(2 \times 2\) matrices with zero trace.

  1. Prove that \(V\) is a subspace of \(M_{2 \times 2}\).
  2. Find a basis and determine the dimension of \(V\).

07: Change of basis and coordinates

Let \(B = \{(3,1), (2,1)\}\) and \(C = \{(1,1), (1,0)\}\) be bases of \(\mathbb{R}^2\).

  1. Find the change-of-basis matrix \(P_{C \leftarrow B}\).
  2. If \([v]_B = (1, 2)^T\), compute \([v]_C\).

Hint: \([v]_B\) notation means that the coordinates of vector \(v\) in basis \(B\) are \((1, 2)^T\) e.g. \(v = 1 \cdot (3,1) + 2 \cdot (2,1)\).

Part 1: Find the change-of-basis matrix \(P_{C \leftarrow B}\)

The columns of the change-of-basis matrix \(P_{C \leftarrow B}\) are the coordinate vectors of the basis vectors in \(B\) relative to the basis \(C\). Let \(\vec{b_1} = (3,1)\), \(\vec{b_2} = (2,1)\), and \(\vec{c_1} = (1,1)\), \(\vec{c_2} = (1,0)\).

We need to express \(\vec{b_1}\) and \(\vec{b_2}\) as linear combinations of \(\vec{c_1}\) and \(\vec{c_2}\).

For \(\vec{b_1} = (3,1)\): We need to find scalars \(x_1, y_1\) such that \((3,1) = x_1(1,1) + y_1(1,0)\). This gives the system: \[ \begin{cases} x_1 + y_1 = 3 \\ x_1 = 1 \end{cases} \] Solving this system yields \(x_1 = 1\) and \(y_1 = 2\). So, \([\vec{b_1}]_C = \begin{pmatrix} 1 \\ 2 \end{pmatrix}\).

For \(\vec{b_2} = (2,1)\): We need to find scalars \(x_2, y_2\) such that \((2,1) = x_2(1,1) + y_2(1,0)\). This gives the system: \[ \begin{cases} x_2 + y_2 = 2 \\ x_2 = 1 \end{cases} \] Solving this system yields \(x_2 = 1\) and \(y_2 = 1\). So, \([\vec{b_2}]_C = \begin{pmatrix} 1 \\ 1 \end{pmatrix}\).

Combining these column vectors gives the change-of-basis matrix: \[ P_{C \leftarrow B} = \begin{pmatrix} 1 & 1 \\ 2 & 1 \end{pmatrix} \]

Part 2: Compute \([v]_C\)

To find the coordinates of \(v\) with respect to basis \(C\), we use the formula: \[ [v]_C = P_{C \leftarrow B} [v]_B \]

Given \([v]_B = \begin{pmatrix} 1 \\ 2 \end{pmatrix}\), we can compute: \[ [v]_C = \begin{pmatrix} 1 & 1 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 \cdot 1 + 1 \cdot 2 \\ 2 \cdot 1 + 1 \cdot 2 \end{pmatrix} = \begin{pmatrix} 1 + 2 \\ 2 + 2 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \end{pmatrix} \]

So, the coordinates of the vector \(v\) in the basis \(C\) are \((3, 4)^T\).

08: Basis verification in different vector spaces

In each case, determine whether \(S\) is a basis for \(V\):

a) \(V = P_3\), \(S = \{0, x, x^2, x^3\}\)

b) \(V = M_{2 \times 2}\), \(S = \left\{I_2, \begin{pmatrix} 1 & 3 \\ 2 & 4 \end{pmatrix}, \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}\right\}\)

c) \(V = \mathbb{R}^3\), \(S = \{e_1, e_2, e_1 + 3e_2\}\)

d) \(V = P_1\), \(S = \{1 - 2x, 2 - x\}\)

09: Linear transformation from coordinates

Linear transformations can be uniquely determined by their values on a basis. This principle is fundamental in neural networks where transformations are defined by weight matrices.

Suppose \(T\) is a linear transformation from \(\mathbb{R}^2\) to \(P_2\) such that: \[T\begin{pmatrix} -1 \\ 1 \end{pmatrix} = x + 3, \quad T\begin{pmatrix} 2 \\ 3 \end{pmatrix} = 2x^2 - x\]

Find \(T\begin{pmatrix} a \\ b \end{pmatrix}\) for arbitrary \(a, b \in \mathbb{R}\).

10: Geometric eigenvalue intuition

Understanding eigenvalues geometrically helps build intuition for principal component analysis, matrix factorizations, and understanding how transformations affect data.

Without doing any calculations, determine the eigenvalues and eigenvectors for the following transformations by thinking about their geometric effects:

  • a) Shear matrix: \(S = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\)

    • What vectors remain on the same line after this transformation?
    • What vectors get stretched or shrunk (and by what factor)?

  • b) Rotation matrix: \(R = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}\) (90° counterclockwise)

  • c) Reflection matrix: \(F = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\) (reflection across x-axis)

  • d) Scaling matrix: \(D = \begin{pmatrix} 3 & 0 \\ 0 & 2 \end{pmatrix}\)

11: Matrix powers using eigenvalues

Consider the matrix \(A = \begin{pmatrix} 5 & 8 \\ 2 & 5 \end{pmatrix}\). We want to compute \(A^{10}\) efficiently.

  1. Find eigenvalues and eigenvectors of matrix \(A\).

  2. Diagonalize the matrix: Express \(A = PDP^{-1}\) where \(D\) is diagonal.

  3. Compute high powers efficiently: Use diagonalization to find \(A^{10}\) without multiplying the matrix 10 times.

  4. Pattern recognition: What happens to \(A^n\) as \(n \to \infty\)? Which eigenvalue dominates?

15: From ellipse equation to eigenanalysis

էս մեկը ընթացիկ ա ուղղակի, ավելի շուտ օպտիմ անելուց ենք նայելու, բայց դե ստեղից չեմ ջնջում որովհետև գուցե ինչ-որ մեկը ուզի հիմիկվանից էլ բզբզա

You are given the equation of an ellipsoid

\[3x^2 + 2y^2 + 2xy\]

Part A: Extract the matrix representation

  1. Rewrite as quadratic form: Express the equation in the form \(\mathbf{v}^T A \mathbf{v}\) where \(\mathbf{v} = \begin{pmatrix} x \\ y \end{pmatrix}\).

  2. Build the symmetric matrix: What is the matrix \(A\)?

Part B: Eigenanalysis

  1. Find eigenvalues and eigenvectors: Compute the eigenvalues \(\lambda_1, \lambda_2\) and their corresponding eigenvectors \(\mathbf{v}_1, \mathbf{v}_2\).

  2. Verify orthogonality: Check that the eigenvectors are orthogonal to each other.

Part C: Geometric interpretation

  1. Principal axes: The eigenvectors represent the principal axes of the ellipse. What are the directions of these axes in the plane?
  1. Sketch and describe:
    • Which axis is the major axis (longer)? Which is the minor axis (shorter)?
    • How is the ellipse oriented relative to the standard x-y coordinate axes?
    • What’s the angle of rotation from the standard axes?

🛠️ Գործնական ToDo

🎲 40 (03)

Flag Counter