F24 ECE 551

HW01, Due 11PM Thu. Sep. 5

Pr. 1.

Let Z(√2) be the set of real number of the form. α + β√2, where α and β are integers. Is Z(√2) a field? Consider sum, multiplication, zero, and unity as they are usually defined in R.

Pr. 2.

Let A be an M × N matrix having elements: aij = i 2 j , for i = 1, . . . , M, j = 1, . . . , N.

(a) Express matrix A mathematically as an outer product of two appropriately defined vectors.

(b) Write (on paper) a one-line Julia expression for creating A when M and N are defined already. Test your Julia expression (just for yourself, not graded).

Pr. 3.

Rewrite the expression

in terms of the N × N matrix A and the vector x ∈ F N whose ith entry is xi .

Check your answer using Julia by trying some random examples.

Hint. Consider u ′v = Σiu ∗ i vi . The left hand side is an expression involving vectors, whereas the RHS is an expression involving elements of those vectors. We often need to go back and forth between these two types of expressions.

Pr. 4.

Vectors u, v, x, y, z are all in R N and we want to compute z*u’*v*x’*y

(a) Rewrite the code with parentheses to ensure the computation is as efficient as possible.

(b) Exactly how many scalar multiplication operations are needed? Explain.

Pr. 5.

Let Σ be an M × N diagonal matrix. Let the diagonal elements of Σ be denoted by σ1, σ2, . . ..

Let U and V be M × M and N × N matrices, respectively. Define A = UΣV ′ .

(a) Suppose M < N: Express A as a sum of outer product matrices where each outer-product matrix is formed from the columns of U and V . How many such outer-product matrices add up to form. A?

(b) Suppose M > N: Express A as a sum of outer-product matrices where each outer-product matrix is formed from the columns of U and V . How many such outer-product matrices add up to form. A?

(c) Generalize the answer above: what is the maximum number of outer-product matrices formed from the columns of U and V , for A = UΣV ′ , that can add up to form. A?

Pr. 6.

Let U1, U2, . . . , Uk ∈ F N×N denote unitary matrices. Show that the product U1U2 · · · Uk is a unitary matrix. Because of this property, the set of N × N unitary matrices over a field F is a group called the orthogonal group denoted O(N, F).

Pr. 7.

Use the defining determinant properties det(A) = det(A⊤) and A, B ∈ R N×N ⇒ det(AB) = det(A) det(B) to solve the following problem. If A is orthogonal, what are the possible values of det(A)?

Pr. 8.

For 30 points, complete the “Julia 101” tutorial at https://pathbird.com/courses/register. (Use the registra-tion code shown on the EECS 551 Canvas home page.) When you reach the end of the tutorial, you will be able to print a concise version (as a pdf file) that shows all your correct answers. Submit that pdf to gradescope. This is an “all or nothing” problem: you earn the credit if and only if you reach the end of the tutorial and submit properly. The introduction you see there might mention “opportunities to work with Python;” that comment applies to EECS 505, not EECS 551.

Pr. 9.

(a) For x, y ∈ F N , prove that det(I − xy′ ) = 1 − y ′x.

Hint. Use the following properties:

• If A, B ∈ F N×N , then det(AB) = det(A) det(B).

• If A ∈ F N×N , then det(A−1 ) = det(A)/1.

• If A ∈ F N×N is invertible and D ∈ FM×M, then

• If A ∈ F N×N and D ∈ FM×M is invertible, then

(b) Express det(λIN − xy′ ) in terms of λ, y ′x, and N.

Hint. Consider writing λIN − xy′ = (λIN ) (IN − λ/xy′) when λ ≠ 0. Also consider the λ = 0 case.

(c) Use the previous step to find all eigenvalues of the matrix xy′ .

(d) When are the eigenvalues of the matrix xy′ all equal to 0 even when the matrix is not equal to zero?

Pr. 10.

For A ∈ F N×N , the trace of A, denoted by Tr(A), is defined as the sum of its diagonal elements: Tr(A) = ΣN i=1 aii.

(a) Show that the trace is a linear function; i.e., if A, B ∈ F N×N and α, β ∈ F, then Tr(αA + βB) = α Tr(A) + β Tr(B).

(b) Show that Tr(AB) = Tr(BA), even though in general AB = BA, when both AB and BA are square.

Your work should be general enough to handle cases where A and B are rectangular.

(c) Let S ∈ R N×N be skew-symmetric, i.e., S T = −S. Show that Tr(S) = 0.

(d) Prove the converse of the previous part, or provide a counterexample.

Pr. 11.

A matrix A ∈ F N×N is called idempotent iff A2 = A.

Show that the matrix is idempotent for all θ.

Hint. Verify that A = vv′ where

Pr. 12.

(a) Determine by hand the eigenvalues of

(b) Compute the determinant and trace of this matrix A.

Compute the product of the eigenvalues of A and the sum of its eigenvalues.

How do these compare to the determinant and the trace?

(c) Check your answers by invoking:

using LinearAlgebra

lambda, V = eigen(A)

Are the eigenvectors (columns of V ) orthogonal?

Display the matrix V ′V and submit a screenshot of the answer.

(d) (not graded)

Some software sorts the eigenvalues in a certain order. What order does Julia return for symmetric matrices?

Pr. 13.

Discrete time convolution (a DSP term) of an input signal x[n] and a filter h[n] is defined in textbooks as:

where the “∗” above denotes convolution, not ordinary multiplication.

In practice we often use finite-length signals and filters, and not all textbooks define this case clearly. The convolution of an input signal (x[0], . . . , x[N − 1]) with a finite impulse response (FIR) filter (h[0], . . . , h[K − 1]) becomes:

This is the type of convolution used in convolutional neural network (CNN) models for machine learning.

Determine M, the length of the (possibly) nonzero part of y, in terms of N and K.

We will use the notation y, h, x to denote the (finite) vectors of length M, K, and N, respectively.

Convolution is a linear operation, so we can express it as a matrix-vector operation of the form. y = Hx where H is a matrix that you must determine and implement in this problem.

With some recycling of notation, you must implement a matrix H such that y = h ∗ x = Hx

Caution: DSP notation uses signals that start at n = 0, whereas the first element of a vector in Julia (and MATLAB) is indexed by 1. This is something you must get used to handling properly.

Hint: It may be helpful to think through carefully the most reasonable size of H first. You should not augment x, nor have any rows that are identically zero in H.

Write a function called convolution that takes as its input the vectors h and x and returns as output both the matrix H and the column vector y (the convolved signal, implemented without conv ).

Hint: Compare your answer with a built-in convolution function: Julia’s conv function (in the DSP package).

In Julia, your file should be named convolution.jl and should contain the following function:

"""

H, y = convolution(h, x)

Compute discrete convolution of the input vectors `h` and `x`

via matrix multiplication,

returning both the matrix `H` and result `y`.

# In:

- `h` vector of length `K`

- `x` vector of length `N`

# Out:

- `H` `M × N` convolution matrix defined by `h`

- `y` vector of length `M` containing the discrete convolution

of `h` and `x` computed using `H`.

"""

function convolution(h, x)

Email your solution as an attachment to [email protected].

The material between the triple quotation marks """ is a Julia docstring and is the preferred way to document code. It supports markdown syntax. With this approach, you can type ?convolution at the REPL or in a Jupyter notebook and see nicely formatted documentation. You are not required to include documentation when submitting code to the autograder, but making clear documentation is important in practice.

Autograder instructions:

Throughout the semester, all coding problems will be graded via an automated system that verifies the correctness of your code by evaluating it on a suite of test cases. To submit your code, simply attach your file to an email (from your @umich.edu account) and send it to: [email protected]. The system will send an email response within a few seconds saying whether your code passes or fails its suite of (typically randomly generated) test cases.

If your code fails: Edit and resubmit your code via the same process. You have unlimited retries.

It is much more intelligent to first write your own test cases rather than trying to use the autograder as a debugger!

Once your code passes: You are done! You will receive full credit for the problem. Do not submit anything to gradescope for this problem! The system already saved an electronic copy for our records. The “pass” email also contains a confirmation code. If we accidentally fail to give you credit for the problem, forward to us the confirmation code and we will record your credit. Points will be posted on Canvas at the end of the term.

Pr. 14.

To see how to use the convolution matrix from the previous problem in an image processing example, see:

https://web.eecs.umich.edu/~fessler/course/551/julia/demo/hw1_show_conv_2d.html

https://web.eecs.umich.edu/~fessler/course/551/julia/demo/hw1_show_conv_2d.ipynb

Modify that notebook to call your own convolution function and see how it works on the 2D image in that notebook.

To use this notebook, you will have to first install the MIRTjim.jl and ImagePhantoms.jl packages by typing

] add MIRTjim

] add ImagePhantoms

Submit a screen shot of your filtered 2D image (the results of 2D convolution) to gradescope.

Your screenshot must include a figure title that shows your name or username.

Caution

When you submit scans of your work to gradescope, be sure to follow the instructions to properly associate submitted work to problems and subproblems. Only work that is submitted properly will be graded! For a class this size it is infeasible to make exceptions. Start the uploading process early to ensure that you have time to submit properly.

Non-graded problem(s) below

(Solutions will be provided for self check; do not submit to gradescope.)

Pr. 15.

Evaluate the following block matrix operations by simplifying the result as much as possible. (For simplicity, you may assume A, B, . . . , H below are all square matrices of the same size. Most of the equalities generalize to rectangular matrices of appropriate sizes.) Below, I2 denotes the 2 × 2 identity matrix.

Even though this problem is not graded, keep in mind that we will use block matrix operations like these very frequently throughout the semester, and block matrices are likely to appear on exams and in your future work.

Pr. 16.

Show that if B, C ∈ FM×N , and if A ∈ F N×N and D ∈ FM×M are invertible, then

det(D + CAB′ ) = det(A−1 + B′D−1C) det(A) det(D).

You may use properties stated or shown in previous problems.