ChapterZero

For what is it possible to have a -regular graph on vertices?

I thought about this a little while last night: it’s equivalent to asking how many hollow (the diagonal is zero) symmetric binary matrices satisfy for all . I haven’t seen a way to exploit this equivalence, so maybe there is another approach that would be more fruitful.

It turns out that if is in , , where depend on the dimension. I have no idea how to prove this in general, and don’t really care.

BUT, it makes for a nice problem in the one-dimensional case. Show that if (i.e. its second derivative exists and both it and its first and second derivatives are square integrable), then , and find .

I haven’t a clue how to proceed, but it looks like mighty fun.

Update: the proof is, in retrospect (always in retrospect, damn it), obvious.

Show that there is no metric on such that pointwise convergence and convergence in the metric coincide.

I finally read up to the Gelfand representation theorem in Murphy’s book. This is such a beautiful mathematical result that I couldn’t resist the urge to share it. I tried to write this synopsis so anyone who understands the Banach-Alaoglu theorem should have no problem following the gist of it.

Recall that a (complex) Banach algebra is a (complex) Banach space with a multiplication operation which is continuous w.r.t. the norm. The Gelfand representation theorem says that we can represent an abelian Banach algebra as the algebra of continuous functions on a locally compact Hausdorff space . The important case to consider is that of a unital Banach algebra, one with an identity element; in this case, we can take the space to be compact. For the remainder, will be a unital abelian complex Banach algebra.

The obvious question is, what is this space ? Can it be intrinsically connected to , or is the proof nonconstructive? It turns out that is a very natural space; in order to construct it, we need the concept of the spectrum of an algebra.

Let . We call the set the spectrum of . One can think of the spectrum as a generalization of the eigenvalues of a square matrix or the range of a bounded function. Recall that a (continuous) homomorphism between two algebras is a linear map which preserves the multiplication operation. A character on is a non-zero homomorphism between and . Let denote the set of characters on ; it turns out, magically, that for all .

One can show that is a weak* closed subset of the unit ball of A*, and in fact if we give the relative weak* topology, it is compact. From here it’s easy to guess that , the character space or spectrum of , is the appropriate . Given , define its Gelfand transform by . By the choice of topology on the character space, each such functional is continuous (and in fact, vanishes at infinity).

The Gelfand representation theorem specialized to unital abelian complex Banach algebras then says

The map is a norm-decreasing homomorphism, and for all . Furthermore, .

Given Rademacher variables , what can we say about
versus ?

Anything?

I came across the following statement while reading Murphy’s book (Theorem 1.3.1): “If is a proper ideal in a Banach algebra, then is also proper.”

Quick recap: a Banach algebra is a Banach space with a multiplication operation, such that the norm is submultiplicative (). A prototypical (non-abelian) finite dimensional Banach space is that of all matrices with the spectral norm, and a prototypical (abelian) infinite dimensional Banach space is that of all continuous functions on with the sup norm. An ideal is a vector subspace that ‘absorbs’ under multiplication: if is in the space and is in the ideal, both and are in the ideal. A proper ideal is one strictly contained in the ambient space.

This statement caught my eye because it gives a way in which ideals topologically differ from vector subspaces. It is easy to come up with examples of proper subspaces whose closures are the entire space; e.g. take the set of differentiable functions in the above infinite dimensional Banach space: every continuous function on is the uniform limit of differentiable functions, so the closure of this subspace is the space itself. It’s harder for me to come up with ideals nontrivially exemplifying the above statement.

The question is: exactly how does one use the multiplicative closure property of ideals to prove the above?

Recall the Schatten p-norm of a matrix : where are the singular values of . They’re interesting, among other reasons, because they’re unitarily invariant. Schatten and Von Neumann came up with these while investigating matrix analogues of the finite spaces— they’re the norms of the vectors of singular values.

Show that , where is the modulus of the matrix.

Note that the Schatten 2-norm (aka Frobenius norm aka Hilbert-Schmidt norm) can be easily calculated , and is actually induced by the inner product . When is positive, show that is also easily calculable: .

Can you show that Schatten -norms have the dual norms you’d expect from analogy with the usual norms? It’s fun

Can you think of any other interesting properties of the Schatten norms?

I spent today looking through several papers. Most of them were about finding graph sparsifiers by sampling– apparently this relates to a generalization of the sparsification problem I’ve been thinking about, where instead of looking for a sparsifier in the spectral norm, you look for one in the norm.

I snuck in a paper by Rudelson and Vershynin, to gain some familiarity with the more typical tools in this area, and came across the neat idea of the numerical rank of a matrix: . It’s clear that this satisfies , but it’s also stable in the sense that if is close to a low rank matrix, then is also low. I’m looking forward to seeing how they use this quantity.

Arghhh!!! I have a meeting tomorrow with my advisor to discuss my progress in research over the past month or so, and I have nothing interesting to mention– partly because I haven’t spent as much time as I could have, but mostly just because I’m slow and dense. I just gave up on the two problems I’ve been looking at, since I’ve gotten nowhere on those, and am now reading his paper on the linear independence of spikes and sines so I can work on another idea he suggested. Namely, to adapt the technique used in the paper to get a bound on the expected spectral norm of a random rectangular submatrix of the Fourier matrix. I can’t get anything done on this tonight besides reading, but it looks interesting.

Question of the night: Let , show that the coefficients of the polynomial satisfy the inequality

It may help to look up Markov’s inequality for polynomials (bounding the derivatives of a polynomial in terms of the Chebyshev polynomials), and try to prove that.