(i) Write down the symmetric matrix Q such that q(x, y）= (x

(ii) Do you expect q(x, y）to be nonnegative for all (x, y）∈ R2 ? write it as a sum of squares by factoring Q as BBT .

(2) We call a real matrix A ∈ Rn×n  skew-symmetric if AT = ━A.

y) Q )y(x)).     Why? If yes,

(a) Give an example of a 3 × 3 skew-symmetric matrix.

(b) Argue that the diagonal elements of any skew-symmetric matrix must be 0.

(c) Argue that if A is a real skew-symmetric matrix then xT Ax = 0 for all x ∈ Rn (Hint: Use the fact that xT Ax is a scalar so that (xT Ax）T = xT Ax).

(d) Here is some background on complex numbers that will help you answer the next      question. We say that a complex number z = a + bi is purely imaginary if a = 0, that  is, z is of the form bi for some b ( R. Recall that the conjugate of z = a + bi is z = a - bi. A complex z is purely imaginary if and only if z = -z . Given a vector x ( Cn  we let x denote the vector whose entries are conjugates of the entries of x. For example if

1(r)   i   1(n)                   1(r)  -i  1(n)

x =   -i      then   x =     i      .

L(1)1 + 2i1(1)                   L(1)1 - 2i1(1)

Just like we did for vectors with real entries, we denote the square norm of a complex vector by xTx = llxll2 . Checking this with our example we get

1(r)   i   1(n)

xTx = [-i   i   1 - 2i]   -i    = -i2 - i2 + (1 + 2i)(1 - 2i) = 7 = llxll2

11 + 2i 1

Recall that the conjugate of a complex number z satisfies z1 z2 = z 1 z2 . Similarly, for matrices and vectors, Ax = Ax.

◆ Argue that the eigenvalues of a real skew-symmetric matrix are purely imaginary.

(Hint: Look at the proof in the notes that real symmetric matrices have real eigenvalues for inspiration. You want to conclude that ━λ = λ.)

(e) Use (d) to argue that if n is odd, then det(A）= 0 and if n is even then det(A）2 0. Give an example where A is invertible.

(3)   (a) Argue that the set of all n × n symmetric matrices forms a subspace of Rn×n . (b) Argue that for n × n matrices,

(i) if A 之 0 and B 之 0, then A＋B 之 0,

(ii) if A 之 0 and λ 2 0 then λA 之 0.

(c) Does the set of all n × n PSD matrices form a subspace in the space of all n × n

symmetric matrices? Explain your reasons.

(4) Recall that the eigenvalues of the Laplacian of a graph on n vertices can be ordered as 0 = λ 1 S λ2 S … S λn . Consider the following graph H:

(a) Write down the Laplacian LH  of the graph H .

(b) Factor LH  as BBT .

(c) Compute the quadratic function xT LH x and write it as a sum of squares.

(d) Find a basis for the eigenspace of LH  corresponding to the eigenvalue 0.

(e) Based on the above which is the first eigenvalue of LH  that is going to be positive?

(f) What is the relationship between the arithmetic multiplicity of the eigenvalue 0 and the number of connected components in a graph? Explain.

(5) * Equiangular lines in Rd . It is important in areas like coding theory to understand the largest number of lines through the origin in Rd  such that the angle between any two of them is the same. A collection of lines through the origin in Rd  such that the the angle between any two of them is the same is a set of equiangular lines. For example, the           maximum number of lines in R3  such that the angle between any two of them is 90o  is 3; take for example the 3 coordinate axes. However, if the common angle is different from    90o  there can be more lines. The 6 diagonals of a regular icosahedron are equiangular.      Google for the regular icosahedron if you have not seen it before.

In the following exercise we will argue that you cannot have more than 6 equiangular lines in R3  no matter what angle θ you choose.

Suppose we have a collection of n equiangular lines in R3  and vi  is a unit vector in the direction of the ith line. It does not matter if you choose vi  or its negative, but choose one and call it vi .

(a) Argue that the condition of equiangularity means that if i ≠ j then vi(T)vj  = cos θ for a fixed angle θ .

(b) You showed last week that the set of all symmetric 3 × 3 matrices form a vector space. Argue that the dimension of this vector space is 6.

Hint: What is a basis of the space of all 2 × 2 symmetric matrices? Then try 3 × 3.

Now consider the rank one PSD matrices vivi(T)  of size 3 × 3.

(c) We will now argue that the rank one psd matrices vivi(T)  of size 3 × 3, coming     from the equiangular lines, are linearly independent (as matrices). This will give us the result since all these rank one psd matrices are in the 6 dimensional vector space of symmetric matrices, so there cannot be more than 6 of them.    This will imply that there cannot be more than 6 lines.

(i) Suppose the matrices vivi(T)  are linearly dependent. Then there are a1 , . . . , an ∈ R such that

S aivivi(T) = 0.