CSE 6040, Fall 2015: Homework 3 -- Linear algebra

The goal of this homework is to force you to read the notes on linear algebra and do a few exercises related to it.

This assignment is due on T-Square by Thursday, October 29 at 11:59pm AOE.

Part 1: Plug and chug [20 points]

Please do the following exercises by hand. You might verify your answers with a calculator or other tool (even Numpy!), but we want you to typeset a response, using a Markdown cell and its embedded LaTeX support.

You may find this website useful for generating LaTeX: http://detexify.kirelabs.org/classify.html

The point of these exercises is just to reinforce some of the definitions from the notes. There shouldn't be anything tricky here.

You may either typeset your responses below, or write them out by hand and scan and upload them as PDF files to T-Square.

Let

$x = \left( \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right)$

and

$A = \left( \begin{array}{ccc} 2 & 1 & 0 \\ 4 & 3 & 1 \\ 6 & 7 & 8 \end{array} \right)$.

Compute the following.

1) $x^T x =$

Here is a free sample answer!

$ \left( \begin{array}{ccc} 1 & 2 & 3 \end{array} \right) \left( \begin{array}{c} 1 \\ 2 \\ 3 \end{array}

\right)

1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3 = 1 + 4 + 9 = 14 $

2) $x x^T =$

3) $\| x \|_1 =$

4) $\| x \|_2 =$

5) $\| x \|_\infty =$

6) $\| A \|_F =$

7) $A^T A =$

8) $A A^T =$

As it happens, the trace of a matrix $M$, or $\mathrm{trace}(M)$, is defined to be the sum of $M$'s diagonal entries. Verify for yourself (i.e., do not turn in!) that

$\mathrm{trace}(A^T A) = \mathrm{trace}(A A^T) = \| A \|_F^2$.

9) Suppose $x$ is now unknown and $b = (1, 1, 1)^T$. Determine a vector $x$ such that $Ax = b$ for the (numerical) matrix $A$ given above. You may use any method, but show your work. (Methods might include basic high school algebra starting from the definitions of a matrix-vector product, or Gaussian elimination, or LU factorization.)

Part 2: A proof [20 points]

Let $Q \in \mathcal{R}^{m \times m}$ be an orthogonal matrix, and let $A \in \mathcal{R}^{m \times n}$ be some matrix. Prove that $\|QA\|_F^2 = \|A\|_F^2$, that is, left-multiplying by an orthogonal matrix does not change the Frobenius norm.

Hint: Consider the definitions of an orthogonal matrix, Frobenius norm, and vector 2-norm. You may also use the fact that $\mathrm{trace}(A^T A) = \|A\|_F^2$ from Part 1, Question 8 above.

Part 3: Solving a linear system in Numpy / SciPy [20 points]

Question 1. [15 points]

Write some Python code that

Creates a random matrix $A \in \mathcal{R}^{1000 \times 1000}$ and a vector $b = [1, 1, \ldots, 1]^T$.
Solves $Ax = b$. You should try to find a Numpy/SciPy call that makes this step relatively easy to do. Use the %timeit directive to measure its execution time.
Computes the inverse of $A$, which is $A^{-1}$. Use the %timeit directive to measure its execution time.



In [ ]:

    
# @YOUSE

Question 2. [5 points]

Explain why these two methods perform at differing speeds.