Given two vectors:

\[ u = \begin{vmatrix} u1 \\ u2 \end{vmatrix} \]

\[ v = \begin{vmatrix} v1 \\ v2 \end{vmatrix} \]

if we project a perpendicular line from (v1, v2) to (u1, u2), meeting at a point with length p from the origin, prove that:

\[\begin{align*} u \cdot v & = p \cdot ||u|| \\ \text{where } u \cdot v & = u_{1} v_{1} + u_{2} v_{2} \text{    (i.e. the inner product)} \end{align*} \]

== Solution ==

Let α and β be the respective angles of v and u from the x-axis:

\[\begin{aligned} p & = ||v|| \space cos (\alpha - \beta) \\ p & = ||v|| \space (cos \space \alpha \space cos \space \beta + sin \space \alpha \space \sin \space \beta) \\ p \cdot ||u|| & = ||v|| \cdot ||u|| \space (cos \space \alpha \space cos \space \beta + sin \space \alpha \space \sin \space \beta) \\ p \cdot ||u|| & = ||v|| \space cos \space \alpha \cdot ||u|| \space cos \space \beta + ||v|| \space sin \space \alpha \cdot ||u|| \space \sin \space \beta \\ p \cdot ||u|| & = v_{1} u_{1} + v_{2} u_{2} \\ p \cdot ||u|| & = u \cdot v \end{aligned} \]

Suppose Q^T equals Q^-1 (transpose equals inverse, so Q^TQ = I).

1. Show that the columns q₁, ..., q_n are unit vectors:

   \[ ||q_{i}||^{2} = 1 \]

2. Show that every two columns of Q are perpendicular:

   \[ q_{1}^{T}q_{2} = 0 \]

3. Find a 2 by 2 example with first entry q₁₁ = cos θ

== Solution ==

1. Observe that:

   \[ ||q_{i}||^{2} \]

   is equal to the dot product of a column by itself, and every element in the resultant matrix of Q^TQ is the dot product of two columns in Q. Since Q^TQ = I, it means when the two columns are the same column in Q, the dot product is equal to 1, corresponding to the diagonal of I.


2. Based on similar observation, every other element in I that doesn't fall on the diagonal corresponds to the dot product of two different columns in Q, and is equal to zero.


3. One obvious example that would work:

   \[ Q = \begin{vmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{vmatrix} \]

   as:

   \[ Q^T Q = \begin{vmatrix} \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{vmatrix} \begin{vmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{vmatrix} = I \]

What are the n-dimensional vectors v = (v₁, · · · , v_n) such that Pv = v for all permutation matrices P ?

== Solution ==

When all the elements in v have the same value ?

Factor the following matrix into PA = LU. Factor it also into A = L₁P₁U₁ (hold the exchange of row 3 until 3 times row 1 is subtracted from row 2):

\[ A = \begin{vmatrix} 0 & 1 & 2 \\ 0 & 3 & 8 \\ 2 & 1 & 1 \\ \end{vmatrix} \]

== Solution ==

To factor into PA = LU, observe that:

\[ \begin{vmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{vmatrix} \space A = \begin{vmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 3 & 8 \\ \end{vmatrix} = L \space \begin{vmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 2 \\ \end{vmatrix} \]

This means:

\[ P = \begin{vmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{vmatrix} \] \[ L = \begin{vmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 \\ \end{vmatrix} \] \[ U = \begin{vmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 2 \\ \end{vmatrix} \]

To factor into A = L₁P₁U₁, observe that:

\[ \begin{vmatrix} 0 & 1 & 2 \\ 0 & 3 & 8 \\ 2 & 1 & 1 \\ \end{vmatrix} \rightarrow L_{1} \begin{vmatrix} 0 & 1 & 2 \\ 0 & 0 & 2 \\ 2 & 1 & 1 \\ \end{vmatrix} = L_{1} P_{1} U_{1} \]

which means:

\[ L_{1} = \begin{vmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \\ \end{vmatrix} \] \[ U_{1} = \begin{vmatrix} 2 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 2 \\ \end{vmatrix} \] \[ P_{1} = \begin{vmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{vmatrix} \]

Compute L and U for the symmetric matrix A:

A = |a a a a|
    |a b b b|
    |a b c c|
    |a b c d|

Find four conditions on a, b, c, d to get A = LU with four pivots.

== Solution ==
|a a a a|    |a   a   a   a|    |a   a   a   a|    |a   a   a   a|
|a b b b| => |  b-a b-a b-a| => |  b-a b-a b-a| => |  b-a b-a b-a| = U
|a b c c|    |  b-a c-a c-a|    |      c-b c-b|    |      c-b c-b| 
|a b c d|    |  b-a c-a d-a|    |      c-b d-b|    |          d-c|
This means:
    |1      |
L = |1 1    |
    |1 1 1  |
    |1 1 1 1|
The four conditions are, obviously,
a != 0
a != b
b != c
c != d

Forward elimination changes:

|1 1|
|   | x = b
|1 2|

to a triangular:

|1 1|
|   | x = c
|0 1|

In other words,

x +  y = 5        x +  y = 5      |1 1 5|      |1 1 5|
             =>                   |     |  =>  |     |
x + 2y = 7             y = 2      |1 2 7|      |0 1 2|

That last subtracted l₂₁ = ___ times row 1 from row 2. The reverse step adds l₂₁ times row 1 to row 2. The matrix for that reverse step is L = ___. Multiply this L times the triangular system:

|1 1|      |5|
|   | x1 = | |
|0 1|      |2|

to get ___ = ___. In letters, L multiplies Ux = c to give ___.

(Fill in the blanks above.)

== Solution ==

That last subtracted l₂₁ = 1 times row 1 from row 2. The reverse step adds l₂₁ times row 1 to row 2. The matrix for that reverse step is

    |1 0|
L = |   |
    |1 1|

Multiply this L times the triangular system:

|1 1|       |5|
|   | x1  = | |
|0 1|       |2|

to get:

|1 0| |1 1|      |1 0| |5|   |5|
|   | |   | x1 = |   | | | = | |
|1 1| |0 1|      |1 1| |2|   |7|

In letters, L multiplies Ux = c to give b.

(This problem is an investigation on a computer.)

• Create an identity matrix (for example, in Octave, I=eye(5)) and a permutation vector (example p=[3 4 1 2 5])
• Create a permutation matrix by permuting the columns (example P=I(:,p))
• Compute matrix powers (P,P^2,P^3,P^4,...)
• Which is the smallest positive power that returns P to the identity ?
• Find five different p's, each with the property that P^k = I, for k = 1,2,3,4,5 and k is the smallest such value
• Hint: when k = 1, the answer is p=[1 2 3 4 5]. When k=5, the answer is p=[2 3 4 5 1]. Now you should find the answers when k=2,3, and 4

== Solution ==

I am sure there exists better solutions.  Anyhow, here is one solved via Python and Octave:

First I generated the 120 permutations via Python, and save the result to a file, permute_5.txt
import itertools
for i in itertools.permutations([1,2,3,4,5]):
    print ' '.join(map(str, i))
Next is the Octave code to find the answers based on the permutation file.
I know the max value of k is 6 via experimentation.
[a b c d e] = textread('permute_5.txt','%d %d %d %d %d');
I = eye(5);
distinct_ks=[0 0 0 0 0 0];
for i = 1:size(a)(1)
    p=[a(i) b(i) c(i) d(i) e(i)];
    P=I(:,p);
    k=1;
    while (!all(all(I == P^k)))
        k = k + 1;
    endwhile
    if distinct_ks(k)
        k
        p
    endif
    distinct_ks(k) = distinct_ks(k) + 1;
endfor
distinct_ks
Here is a summary of the interesting results:
P^1 == I when p = [1 2 3 4 5]
P^2 == I when p = [1 2 3 5 4]
P^3 == I when p = [1 2 4 5 3]
P^4 == I when p = [1 3 4 5 2]
P^5 == I when p = [2 3 4 5 1]
P^6 == I when p = [2 1 4 5 3]
Distributions:
k       : 1    2    3    4    5    6
P^k == I: 1   25   20   30   24   20

By trial and error find real non-zero 2 by 2 matrices such that:

1. A^2 = -I

2. BC = 0

3. DE = -ED (not allowing DE = 0)

== Solutions ==
Observe:
      |a b|^2   |a^2+bc ab+bd |        |-1  0|
A^2 = |   |   = |             | = -I = |     |
      |c d|     |ac+cd  bc+d^2|        |0  -1|
which means bc must be negative.  Trying the simplest case by setting a and d to zeros:
    |0  1|    
A = |    |
    |-1 0|
which turns out to work.  This means -A is also a solution.  Do you see why ?

We can interpret BC=0 as finding C such that the linear combination of the columns of B is zero.
Try a simple case when B is all ones:
     |1 1|| 1  1|
BC = |   ||     | = 0
     |1 1||-1 -1|
which is one solution.

This is the challenging one among the three.  In details, it means:
|a b||a' b'|    |a' b'||a b|
|   ||     | = -|     ||   |
|c d||c' d'|    |c' d'||c d|
This means 4 conditions must be satisfied:
2aa'      + bc' + b'c = 0
2dd'      + bc' + b'c = 0
ab' + ab' + bd' + b'd = 0
ac' + a'c + cd' + c'd = 0
From the first 2 equations, it also means aa' must equal dd'.
For example, if a=a'=1, dd' must be 1.  Let's try d=d'=-1:
|1   ||1   |
|  -1||  -1|
Now 2aa' = 2, (bc' + b'c) must equal -2 for the first equation to hold.
Try the simple case when bc' = -2 and b'c = 0, which implies either b' or c must be zero.
Let's try c = 0:
|1  1||1  b'|
|0 -1||-2 -1|
whatever b' value is, this turns out to work!  We can check the result using Octave:
D = [1 1; 0 -1]
E = [1 rand(); -2 -1]
Both:
D*E != 0
D*E == -E*D
would always result in all ones :-)

The parabola:

y = ax + bx + cx^2

goes through the points:

(x,y) = (1,4), (2,8), and (3,14)

Find and solve a matrix equation for the unknowns (a, b, c)

== Solution ==

Given:
a +  b +  c = 4
a + 2b + 4c = 8
a + 3b + 9c = 14
Representing these equations as matrix in Octave:
A = [1 1 1; 1 2 4; 1 3 9]
b = [4; 8; 14]
Solving x for Ax = b:
A\b
Outputs:
2
1
1
which means:
a=2, b=1, c=1

What 2 by 2 matrix R rotates every vector through 45 degree ? The vector (1,0) goes to (√2/2, √2/2). The vector (0,1) goes to (-√2/2,√/2).

== Solution ==

Consider (x,y) as:

  x = k * cos(α)
  y = k * sin(α)

where k is the distance from (0,0) and α the angle from x-axis.

Rotating it through 45 degree:

  x = k * cos(α + π/4)
  y = k * sin(α + π/4)

By trigonometric identities,

  x = k * [cos(α) * cos(π/4) - sin(α) * sin(π/4)]
    = k * [cos(α) - sin(α)] / √2
    = (x - y) / √2

  y = k * [sin(α) * cos(π/4) + cos(α) * sin(π/4)]
    = k * [sin(α) + cos(α)] / √2
    = (x + y) / √2

What matrix would act on (x,y) to yield (x-y, x+y) ?

   |1 -1||x|   |x-y|
   |    || | = |   |
   |1  1||y|   |x+y|

So the answer is:

   |1/√2 -1/√2|
   |1/√2  1/√2|