Matrix computations &
Numerical linear algebra

David Gleich

Purdue University

Fall 2012

Course number CS-51500

Tuesday and Thursday, 10:30-11:45am

Location Lawson 1106

Homework 1

$\newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\tvec}{vec} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

Homework 1

Please answer the following questions in complete sentences in a clearly prepared manuscript and submit the solution by the end of class on Thursday, September 6th, 2012.

Problem 0: List your collaborators.

Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale. (Note that collaboration is not allowed on the bonus question below.)

Problem 1: Operations

Compute the following by hand or using Matlab.

a) $\bmat{ 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 } \bmat{ 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9} =$ ?

b) $\vx =$ ones(1000,1) $\vy =$ [1:1000]' $\vx^T \vy =$ ?

(Optional extra question – worth no points – who is always credited with discovering a very efficient way to compute this as a child?)

c) $\vx = \bmat{ 5 & 3 & -1}^T$, $\ve \vx^T =$ ? $\vx \ve^T =$ ?

d) $\vx = \bmat{1 & 2 & 3}^T$, $\ve_1 \vx^T =$ ? $\vx \ve_3^T =$ ?

Problem 2: A proof

Let $\mA$ and $\mC$ be invertible matrices. We’ll prove that the inverse of $\bmat{ \mA & \mB \\ 0 & \mC }$ is easy to determine!

a) Show that the inverse of

$$\bmat{ 1 & a \\ 0 & 1 }$$

is

$$\bmat{ 1 & -a \\ 0 & 1 }.$$

b) Now, show that the inverse of

$$\bmat{ \mI & \mA \\ 0 & \mI }$$

is

$$\bmat{ \mI & -\mA \\ 0 & \mI }.$$

c) Recall that for general $\mA$ and $\mB$, not those in the problem!, $(\mA \mB)^{-1} = \mB^{-1} \mA^{-1}$. Use this fact, and the result of problem b to determine the inverse to $\bmat{ \mA & \mB \\ 0 & \mC }$ when $\mA$ and $\mC$ are invertible. Alternatively, give the inverse of $\bmat{ \mA & \mB \\ 0 & \mC }$. Hint: think about diagonal matrices!

Problem 3: Image downsampling

This problem will be more difficult if you haven’t used Matlab before, so get started early! It’s designed to teach you about writing for loops to construct a matrix operation for a particular task.

Consider the following problem. We have a $32 \times 32$ pixel image. Each pixel is a real-valued number between $0$ and $1$. However, I want to show this on an iPhone and I only have a $16 \times 16$ pixel area to show the image. In order to reduce the size of the image, I want to average groups of 4 pixels. In this problem, we’ll create a Matlab program to do this

Let’s work through a smaller example first. For the $4 \times 4$ image, represented here by a matrix-like array:

$$\bmat{ x_{1} & x_2 & x_3 & x_4 \\ x_5 & x_6 & x_7 & x_8 \\ x_9 & x_{10} & x_{11} & x_{12} \\ x_{13} & x_{14} & x_{15} & x_{16} }$$

I want to compute

$$\bmat{ (x_1 + x_2 + x_5 + x_6)/4 & (x_3 + x_4 + x_7 + x_8)/4 \\ (x_9 + x_{10} + x_{13} + x_{14})/4 & (x_{11} + x_{12} + x_{15} + x_{16})/4 }.$$

We will solve this problem using a matrix-vector product.

a) Suppose I call:

$$\begin{matrix} y_1 = (x_1 + x_2 + x_5 + x_6)/4 & y_2 = (x_3 + x_4 + x_7 + x_8)/4 \\ y_3 = (x_9 + x_{10} + x_{13} + x_{14})/4 & y_4 = (x_{11} + x_{12} + x_{15} + x_{16})/4. \end{matrix}$$

Further, suppose we consider the vectors $\vy \in \RR^{4}$ and $\vx \in \RR^{16}$ to be the new image and old image, respectively. Write down the matrix $\mA$ such that $\vy = \mA \vx$.

In the remainder of the problem, we’ll work through how to do this for a particular image in Matlab.

b) Download http://www.cs.purdue.edu/homes/dgleich/cs515/homeworks/smallicon.mat and type

load smallicon.mat 

in Matlab. You should get a $32 \times 32$ matrix $\mX$. What is the sum of diagonal elements of $\mX$? (If you wish to use another programming language, feel free, but make sure you can do the same things in it. I’ve provided http://www.cs.purdue.edu/homes/dgleich/cs515/homeworks/smallicon.txt as a text file for use in other languages.)

c) Matlab has a command for viewing a matrix as an image. Run the following commands:

imagesc(X)

The result looks really weird, right? That’s because Matlab is making up a color for each pixel. We can tell it to use a greyscale colormap by executing:

colormap(gray)

Save the resulting Matlab figure as an image to include in your homework. (You’ll need to do this for future homeworks, so make sure you know how to do it on this one!)

d) In what follows, we’ll talk about two different types of indices. The image index of a pixel is a pair $(i,j)$ that identifies a row and column for the pixel in the image. The vector index of a pixel is the index of that pixel in a linear ordering of the image elements. For instance, above, pixel (3,2) has linear index $10$. Also, pixel (1,4) has index $4$. Matlab can help us built a map between pixel indices and linear or vector indices:

N = reshape(1:(4*4), 4, 4)';

This creates the pixel index to linear index for the problem above because

N(1,4) 
N(3,2)

return the appropriate entry.

In your own words, explain what the reshape operation does. What happens if you omit the final transpose above and try:

N = reshape(1:(4*4), 4, 4);

instead?

e) Now we need to construct the matrix $\mA$ in order to reduce the size of $\mX$. Suppose we call the output vector $\vy$ and the output image $\mY$. I’m giving you the following template, that I hope you can fill in. Feel free to construct $\mA$ any way you choose, but the following should provide some guidance.

NX = <fill in>; % the map between pixel indices and linear indices for X
NY = <fill in>; % the map between pixel indices and linear indices for Y
for i=1:32
    for j=1:32    
        xi = <fill in>; % the index of the pixel i,j in the vector x
        yij = <fill in>; % the resulting location of pixel in the matrix Y
        yi = <fill in>; % the index of the linear pixel in the vector y
        
        A(yi,xi) = 1/4; % place the entry of the matrix
    end
 end

f) In order to use the matrix $\mA$ we created, we need to convert the matrix $\mX$ into a vector! The reshape operation helps here:

x = reshape(X',32*32,1);

We can now rescale the image $\mX$ by multiplying by $\mA$ and reorganizing back into a matrix $\mY$.

y = A*x;
Y = reshape(y,16,16)';

Show the image of $\mY$. Does that look correct?

g) The Matlab way to solve this problem is to use the built in routine interp2. In this case, you can call

Ym = interp2(X,-1)

to accomplish the same goal and save the output to a Matlab variable Ym.

Do Y and Ym agree? If not, can you comment on their differences?

h) Show all of your code for this problem.

Problem 4: Prove or disprove

For the following questions, either prove that the statement is correct, or show a counter-example.

a) The product of two diagonal matrices is diagonal.

b) The product of two upper triangular matrices is upper triangular

c) The product of two symmetric matrices is symmetric.

d) The product of two orthogonal matrices is orthogonal.

Problem 5

There are a tremendous number of matrix norms that arise. An interesting class are called the orthgonally invariant norms. Norms in this class satisfy:

$$\normof{\mA} = \normof{\mU \mA \mV}$$

for square orthogonal matrices $\mU$ and $\mV$. Recall that a square matrix is orthogonal when $\mU^T \mU = \mI$, i.e. $\mU^{-1} = \mU^T$.

Show that $\normof{ \mA }_2$ is orthogonally invariant.

Problem 6

Consider the following function:

$$f(\mA) = \max_{i,j} |A_{i,j}|.$$

 

a) Show that $f$ is a matrix norm.

b) Show that $f$ does not satisfy the sub-multiplicative property.