Matematički blogovi

Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra

Terrence Tao - Sri, 2019-12-04 04:20

Peter Denton, Stephen Parke, Xining Zhang, and I have just uploaded to the arXiv a completely rewritten version of our previous paper, now titled “Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra“. This paper is now a survey of the various literature surrounding the following basic identity in linear algebra, which we propose to call the eigenvector-eigenvalue identity:

Theorem 1 (Eigenvector-eigenvalue identity) Let be an Hermitian matrix, with eigenvalues . Let be a unit eigenvector corresponding to the eigenvalue , and let be the component of . Then

where is the Hermitian matrix formed by deleting the row and column from .

When we posted the first version of this paper, we were unaware of previous appearances of this identity in the literature; a related identity had been used by Erdos-Schlein-Yau and by myself and Van Vu for applications to random matrix theory, but to our knowledge this specific identity appeared to be new. Even two months after our preprint first appeared on the arXiv in August, we had only learned of one other place in the literature where the identity showed up (by Forrester and Zhang, who also cite an earlier paper of Baryshnikov).

The situation changed rather dramatically with the publication of a popular science article in Quanta on this identity in November, which gave this result significantly more exposure. Within a few weeks we became informed (through private communication, online discussion, and exploration of the citation tree around the references we were alerted to) of over three dozen places where the identity, or some other closely related identity, had previously appeared in the literature, in such areas as numerical linear algebra, various aspects of graph theory (graph reconstruction, chemical graph theory, and walks on graphs), inverse eigenvalue problems, random matrix theory, and neutrino physics. As a consequence, we have decided to completely rewrite our article in order to collate this crowdsourced information, and survey the history of this identity, all the known proofs (we collect seven distinct ways to prove the identity (or generalisations thereof)), and all the applications of it that we are currently aware of. The citation graph of the literature that this ad hoc crowdsourcing effort produced is only very weakly connected, which we found surprising:

The earliest explicit appearance of the eigenvector-eigenvalue identity we are now aware of is in a 1966 paper of Thompson, although this paper is only cited (directly or indirectly) by a fraction of the known literature, and also there is a precursor identity of Löwner from 1934 that can be shown to imply the identity as a limiting case. At the end of the paper we speculate on some possible reasons why this identity only achieved a modest amount of recognition and dissemination prior to the November 2019 Quanta article.

Kategorije: Matematički blogovi

Hédi Daboussi, in memoriam

E. Kowalski's blog - Pet, 2019-11-29 18:24

I was very sad to learn today from R. de la Bretèche and É. Fouvry that Hédi Daboussi passed away yesterday. Hédi played an important part in my life; he was the first actual analytic number theorist that I met, one day at IHP in 1987, at the beginning of my first bachelor-thesis style project. (This was before internet was widely available.) Fouvry and him advised me on this project, which was devoted to the large sieve, especially the proof of Selberg based on the Beurling functions. They also introduced me to Henryk Iwaniec, who was visiting Orsay at the time (in fact, the meeting at IHP was organized to coincide with a talk of Iwaniec).

Daboussi is probably best known outside the French analytic number theory community for two things: his elegant elementary proof of the Prime Number Theorem, found in 1983, which does not use Selberg’s identity, and which is explained in the nice book of Mendès-France and Tenenbaum, and the “Rencontres de théorie élémentaire et analytique des nombres”, which he organized for a long time as a weekly seminar in Paris, before they were transformed, after his retirement, into (roughly) monthly meetings, which are still known as the “Journées Daboussi”, and are organized by Régis de la Bretèche. The first of these were two days of a meeting in 2006 in honor of Hédi.

For me, the original Monday seminar organized by Daboussi was especially memorable, both because I gave my first “real” mathematics lecture there (I think that it was about my bachelor project), and also because on another occasion (either the same time or close to that), I first met Philippe Michel in Hédi’s seminar. It is very obvious to me that, without him, my life would have been very different, and I will always remember him because of that.

Kategorije: Matematički blogovi

An uncountable Moore-Schmidt theorem

Terrence Tao - Čet, 2019-11-28 16:47

Asgar Jamneshan and I have just uploaded to the arXiv our paper “An uncountable Moore-Schmidt theorem“. This paper revisits a classical theorem of Moore and Schmidt in measurable cohomology of measure-preserving systems. To state the theorem, let be a probability space, and be the group of measure-preserving automorphisms of this space, that is to say the invertible bimeasurable maps that preserve the measure : . To avoid some ambiguity later in this post when we introduce abstract analogues of measure theory, we will refer to measurable maps as concrete measurable maps, and measurable spaces as concrete measurable spaces. (One could also call a concrete probability space, but we will not need to do so here as we will not be working explicitly with abstract probability spaces.)

Let be a discrete group. A (concrete) measure-preserving action of on is a group homomorphism from to , thus is the identity map and for all . A large portion of ergodic theory is concerned with the study of such measure-preserving actions, especially in the classical case when is the integers (with the additive group law).

Let be a compact Hausdorff abelian group, which we can endow with the Borel -algebra . A (concrete measurable) –cocycle is a collection of concrete measurable maps obeying the cocycle equation

for -almost every . (Here we are glossing over a measure-theoretic subtlety that we will return to later in this post – see if you can spot it before then!) Cocycles arise naturally in the theory of group extensions of dynamical systems; in particular (and ignoring the aforementioned subtlety), each cocycle induces a measure-preserving action on (which we endow with the product of with Haar probability measure on ), defined by

This connection with group extensions was the original motivation for our study of measurable cohomology, but is not the focus of the current paper.

A special case of a -valued cocycle is a (concrete measurable) -valued coboundary, in which for each takes the special form

for -almost every , where is some measurable function; note that (ignoring the aforementioned subtlety), every function of this form is automatically a concrete measurable -valued cocycle. One of the first basic questions in measurable cohomology is to try to characterize which -valued cocycles are in fact -valued coboundaries. This is a difficult question in general. However, there is a general result of Moore and Schmidt that at least allows one to reduce to the model case when is the unit circle , by taking advantage of the Pontryagin dual group of characters , that is to say the collection of continuous homomorphisms to the unit circle. More precisely, we have

Theorem 1 (Countable Moore-Schmidt theorem) Let be a discrete group acting in a concrete measure-preserving fashion on a probability space . Let be a compact Hausdorff abelian group. Assume the following additional hypotheses:

Then a -valued concrete measurable cocycle is a concrete coboundary if and only if for each character , the -valued cocycles are concrete coboundaries.

The hypotheses (i), (ii), (iii) are saying in some sense that the data are not too “large”; in all three cases they are saying in some sense that the data are only “countably complicated”. For instance, (iii) is equivalent to being second countable, and (ii) is equivalent to being modeled by a complete separable metric space. It is because of this restriction that we refer to this result as a “countable” Moore-Schmidt theorem. This theorem is a useful tool in several other applications, such as the Host-Kra structure theorem for ergodic systems; I hope to return to these subsequent applications in a future post.

Let us very briefly sketch the main ideas of the proof of Theorem 1. Ignore for now issues of measurability, and pretend that something that holds almost everywhere in fact holds everywhere. The hard direction is to show that if each is a coboundary, then so is . By hypothesis, we then have an equation of the form

for all and some functions , and our task is then to produce a function for which

for all .

Comparing the two equations, the task would be easy if we could find an for which

for all . However there is an obstruction to this: the left-hand side of (3) is additive in , so the right-hand side would have to be also in order to obtain such a representation. In other words, for this strategy to work, one would have to first establish the identity

for all . On the other hand, the good news is that if we somehow manage to obtain the equation, then we can obtain a function obeying (3), thanks to Pontryagin duality, which gives a one-to-one correspondence between and the homomorphisms of the (discrete) group to .

Now, it turns out that one cannot derive the equation (4) directly from the given information (2). However, the left-hand side of (2) is additive in , so the right-hand side must be also. Manipulating this fact, we eventually arrive at

In other words, we don’t get to show that the left-hand side of (4) vanishes, but we do at least get to show that it is -invariant. Now let us assume for sake of argument that the action of is ergodic, which (ignoring issues about sets of measure zero) basically asserts that the only -invariant functions are constant. So now we get a weaker version of (4), namely

for some constants .

Now we need to eliminate the constants. This can be done by the following group-theoretic projection. Let denote the space of concrete measurable maps from to , up to almost everywhere equivalence; this is an abelian group where the various terms in (5) naturally live. Inside this group we have the subgroup of constant functions (up to almost everywhere equivalence); this is where the right-hand side of (5) lives. Because is a divisible group, there is an application of Zorn’s lemma (a good exercise for those who are not acquainted with these things) to show that there exists a retraction , that is to say a group homomorphism that is the identity on the subgroup . We can use this retraction, or more precisely the complement , to eliminate the constant in (5). Indeed, if we set

then from (5) we see that

while from (2) one has

and now the previous strategy works with replaced by . This concludes the sketch of proof of Theorem 1.

In making the above argument rigorous, the hypotheses (i)-(iii) are used in several places. For instance, to reduce to the ergodic case one relies on the ergodic decomposition, which requires the hypothesis (ii). Also, most of the above equations only hold outside of a set of measure zero, and the hypothesis (i) and the hypothesis (iii) (which is equivalent to being at most countable) to avoid the problem that an uncountable union of sets of measure zero could have positive measure (or fail to be measurable at all).

My co-author Asgar Jamneshan and I are working on a long-term project to extend many results in ergodic theory (such as the aforementioned Host-Kra structure theorem) to “uncountable” settings in which hypotheses analogous to (i)-(iii) are omitted; thus we wish to consider actions on uncountable groups, on spaces that are not standard Borel, and cocycles taking values in groups that are not metrisable. Such uncountable contexts naturally arise when trying to apply ergodic theory techniques to combinatorial problems (such as the inverse conjecture for the Gowers norms), as one often relies on the ultraproduct construction (or something similar) to generate an ergodic theory translation of these problems, and these constructions usually give “uncountable” objects rather than “countable” ones. (For instance, the ultraproduct of finite groups is a hyperfinite group, which is usually uncountable.). This paper marks the first step in this project by extending the Moore-Schmidt theorem to the uncountable setting.

If one simply drops the hypotheses (i)-(iii) and tries to prove the Moore-Schmidt theorem, several serious difficulties arise. We have already mentioned the loss of the ergodic decomposition and the possibility that one has to control an uncountable union of null sets. But there is in fact a more basic problem when one deletes (iii): the addition operation , while still continuous, can fail to be measurable as a map from to ! Thus for instance the sum of two measurable functions need not remain measurable, which makes even the very definition of a measurable cocycle or measurable coboundary problematic (or at least unnatural). This phenomenon is known as the Nedoma pathology. A standard example arises when is the uncountable torus , endowed with the product topology. Crucially, the Borel -algebra generated by this uncountable product is not the product of the factor Borel -algebras (the discrepancy ultimately arises from the fact that topologies permit uncountable unions, but -algebras do not); relating to this, the product -algebra is not the same as the Borel -algebra , but is instead a strict sub-algebra. If the group operations on were measurable, then the diagonal set

would be measurable in . But it is an easy exercise in manipulation of -algebras to show that if are any two measurable spaces and is measurable in , then the fibres of are contained in some countably generated subalgebra of . Thus if were -measurable, then all the points of would lie in a single countably generated -algebra. But the cardinality of such an algebra is at most while the cardinality of is , and Cantor’s theorem then gives a contradiction.

To resolve this problem, we give a coarser -algebra than the Borel -algebra, which we call the reduced -algebra , thus coarsening the measurable space structure on to a new measurable space . In the case of compact Hausdorff abelian groups, can be defined as the -algebra generated by the characters ; for more general compact abelian groups, one can define as the -algebra generated by all continuous maps into metric spaces. This -algebra is equal to when is metrisable but can be smaller for other . With this measurable structure, becomes a measurable group; it seems that once one leaves the metrisable world that is a superior (or at least equally good) space to work with than for analysis, as it avoids the Nedoma pathology. (For instance, from Plancherel’s theorem, we see that if is the Haar probability measure on , then (thus, every -measurable set is equivalent modulo -null sets to a -measurable set), so there is no damage to Plancherel caused by passing to the reduced -algebra.

Passing to the reduced -algebra fixes the most severe problems with an uncountable Moore-Schmidt theorem, but one is still faced with an issue of having to potentially take an uncountable union of null sets. To avoid this sort of problem, we pass to the framework of abstract measure theory, in which we remove explicit mention of “points” and can easily delete all null sets at a very early stage of the formalism. In this setup, the category of concrete measurable spaces is replaced with the larger category of abstract measurable spaces, which we formally define as the opposite category of the category of -algebras (with Boolean algebra homomorphisms). Thus, we define an abstract measurable space to be an object of the form , where is an (abstract) -algebra and is a formal placeholder symbol that signifies use of the opposite category, and an abstract measurable map is an object of the form , where is a Boolean algebra homomorphism and is again used as a formal placeholder; we call the pullback map associated to .  [UPDATE: It turns out that this definition of a measurable map led to technical issues.  In a forthcoming revision of the paper we also impose the requirement that the abstract measurable map be -complete (i.e., it respects countable joins).] The composition of two abstract measurable maps , is defined by the formula , or equivalently .

Every concrete measurable space can be identified with an abstract counterpart , and similarly every concrete measurable map can be identified with an abstract counterpart , where is the pullback map . Thus the category of concrete measurable spaces can be viewed as a subcategory of the category of abstract measurable spaces. The advantage of working in the abstract setting is that it gives us access to more spaces that could not be directly defined in the concrete setting. Most importantly for us, we have a new abstract space, the opposite measure algebra of , defined as where is the ideal of null sets in . Informally, is the space with all the null sets removed; there is a canonical abstract embedding map , which allows one to convert any concrete measurable map into an abstract one . One can then define the notion of an abstract action, abstract cocycle, and abstract coboundary by replacing every occurrence of the category of concrete measurable spaces with their abstract counterparts, and replacing with the opposite measure algebra ; see the paper for details. Our main theorem is then

Theorem 2 (Uncountable Moore-Schmidt theorem) Let be a discrete group acting abstractly on a -finite measure space . Let be a compact Hausdorff abelian group. Then a -valued abstract measurable cocycle is an abstract coboundary if and only if for each character , the -valued cocycles are abstract coboundaries.

With the abstract formalism, the proof of the uncountable Moore-Schmidt theorem is almost identical to the countable one (in fact we were able to make some simplifications, such as avoiding the use of the ergodic decomposition). A key tool is what we call a “conditional Pontryagin duality” theorem, which asserts that if one has an abstract measurable map for each obeying the identity for all , then there is an abstract measurable map such that for all . This is derived from the usual Pontryagin duality and some other tools, most notably the completeness of the -algebra of , and the Sikorski extension theorem.

We feel that it is natural to stay within the abstract measure theory formalism whenever dealing with uncountable situations. However, it is still an interesting question as to when one can guarantee that the abstract objects constructed in this formalism are representable by concrete analogues. The basic questions in this regard are:

  • (i) Suppose one has an abstract measurable map into a concrete measurable space. Does there exist a representation of by a concrete measurable map ? Is it unique up to almost everywhere equivalence?
  • (ii) Suppose one has a concrete cocycle that is an abstract coboundary. When can it be represented by a concrete coboundary?

For (i) the answer is somewhat interesting (as I learned after posing this MathOverflow question):

  • If does not separate points, or is not compact metrisable or Polish, there can be counterexamples to uniqueness. If is not compact or Polish, there can be counterexamples to existence.
  • If is a compact metric space or a Polish space, then one always has existence and uniqueness.
  • If is a compact Hausdorff abelian group, one always has existence.
  • If is a complete measure space, then one always has existence (from a theorem of Maharam).
  • If is the unit interval with the Borel -algebra and Lebesgue measure, then one has existence for all compact Hausdorff assuming the continuum hypothesis (from a theorem of von Neumann) but existence can fail under other extensions of ZFC (from a theorem of Shelah, using the method of forcing).
  • For more general , existence for all compact Hausdorff is equivalent to the existence of a lifting from the -algebra to (or, in the language of abstract measurable spaces, the existence of an abstract retraction from to ).
  • It is a long-standing open question (posed for instance by Fremlin) whether it is relatively consistent with ZFC that existence holds whenever is compact Hausdorff.

Our understanding of (ii) is much less complete:

  • If is metrisable, the answer is “always” (which among other things establishes the countable Moore-Schmidt theorem as a corollary of the uncountable one).
  • If is at most countable and is a complete measure space, then the answer is again “always”.

In view of the answers to (i), I would not be surprised if the full answer to (ii) was also sensitive to axioms of set theory. However, such set theoretic issues seem to be almost completely avoided if one sticks with the abstract formalism throughout; they only arise when trying to pass back and forth between the abstract and concrete categories.

Kategorije: Matematički blogovi

New Theorems

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorems no. 247-248
Kategorije: Matematički blogovi

New Theorems

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorems no. 249-251
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 228, 229, 230, by R.A. Fisher, Poncelet and Ore
Kategorije: Matematički blogovi

New Theorems

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 231, 232, 233, 234
Kategorije: Matematički blogovi

New Theorems

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 235, 236, 237
Kategorije: Matematički blogovi

New Theorems

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 238 and 239
Kategorije: Matematički blogovi

New Theorems

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 240 and 241
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has a 'new acquisition': Theorem no. 242, the Polya-Redfield Enumeration Theorem
Kategorije: Matematički blogovi

New Theorems

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorems no. 243-246
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has a 'new acquisitions': Theorem no. 227, Cauchy's Theorem in Group Theory
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has a 'new acquisitions': Theorem no. 226, Wolstenholme's Theorem
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 223, 224, 225, by Tutte, Green and Regiomontanus
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has a 'new acquisitions': Theorem no. 222, Faulhaber's Formula
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has a 'new acquisitions': Theorem no. 221, the Inclusion-Exclusion Principle
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 218, Riemann Rearrangement Theorem no. 219, Integration by Parts, and Theorem no. 220, the Pappus-Guldin Theorems
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has 'new acquisitions': Theorem no. 216, Irrationality of Unit Circle Circumference and Theorem no. 217, Taylor's Theorem
Kategorije: Matematički blogovi

New Theorem

Theorem of the Day - Sri, 2019-11-20 16:40
Theorem of the Day has a 'new acquisition': Theorem no. 215, Wedderburn's Little Theorem
Kategorije: Matematički blogovi