A complex analytic proof of the Cayley-Hamilton theorem

The Cayley-Hamilton theorem states that any real or complex square matrix satisfies its own characteristic equation. Hamilton originally proved a version involving quaternions, which can be represented by {4\times 4} real matrices. A few years later, Cayley established it for {3\times 3} matrices. It was Frobenius who established the general case more than 20 years later. (The theorem is also valid for a matrix over commutative rings in general.)

There are many nice proofs of Cayley-Hamilton. Doron Zeilberger‘s exposition of the combinatorial proof of Howard Straubing comes to mind. To my taste, one of the nicest proofs, due to Charles A. McCarthy, uses a matrix version of Cauchy’s integral formula. Here I expand on McCarthy’s original proof, and also have borrowed from  Leandro Cioletti‘s exposition on the subject.

We first state the theorem. Let {A} be an {n\times n} matrix over the real or complex fields {\Bbb R} or {\Bbb C}. Let {I_n} be the identity matrix. The characteristic polynomial {p(t)} for the variable {t} and matrix {A} is defined as

\displaystyle p(t)= \det (t I_n -A )~. \ \ \ \ \ (1)

The charactetristic equation for {A} is defined as

\displaystyle p(t)=0~. \ \ \ \ \ (2)

In the past this equation was sometimes known as the secular equation. The degree of {p} is clearly {n}. The Cayley-Hamilton theorem states that

\displaystyle p(A) =0~. \ \ \ \ \ (3)

In other words {A} satisfies its own characteristic equation.

Note that if {A} is diagonal, {p(A)=0} is clearly satisfied, because the diagonal entries {A_{ii}} are just the eigenvalues, which necessarily satisfy the characteristic equation. If {A} is not diagonal but is diagonalizable, then also the theorem is clearly true, because the determinant is invariant under similarity transformations. But what about the general case, which includes all the non-diagonalizable matrices? This general case is what makes the theorem non-trivial to prove.

We can prove the theorem using a continuity argument. Recall that every matrix {A} with non-degenerate eigenvalues is diagonalizable. So we can approximate every non-diagonalizable matrix to arbitrary precision in terms of a diagonalizable matrix. This qualitative statement can be made precise. Specifically, the diagonalizable matrices are dense in the set of all square matrices. Since the determinant is a continuous function of {A}, therefore {p(A)} cannot discontinuously jump away from zero as {A} is varied continuously — thus establishing Cayley-Hamilton for the general case. There are many variations of this theme.

The reason that I very much like McCarthy’s complex analytic proof is that it uses the Cauchy integral formula to implement this continuity argument without ever explicitly invoking continuity. This is possible because Cauchy’s integral formula allows a function to be calculated at a point without ever having to evaluate the function explicitly at that point. So the value of {p(A)} can be calculated for non-diagonalizable matrices without actually having to compute {p(A)} directly. It is a beautiful proof.

In what follows, I give a step-by-step reproduction of McCarthy’s proof. I assume that readers have familiarity with Cauchy’s integral formula for complex functions of a single complex variable. For our purposes, let {f: \Bbb C \rightarrow \Bbb C} be entire. Then Cauchy’s integral formula states that

\displaystyle f(a) = \frac 1 {2 \pi i } \oint \frac{f(z)}{z-a} ~dz ~. \ \ \ \ \ (4)

Proofs are found in standard texts. Here we will need the following version for matrices. Let {A} be an {n\times n} matrix with entries in {\Bbb C}. Then

\displaystyle f(A) = \frac 1 {2 \pi i } \oint \frac{f(z)}{z I_n -A} ~dz ~, \ \ \ \ \ (5)

where {I_n} is the identity matrix. See the appendix below for a simple proof.

Recall that the inverse {B^{-1}} of an invertible matrix {B} is given by

\displaystyle B^{-1} = \frac {{\rm adj} (B)} {\det (B)} \ \ \ \ \ (6)

wbere {{\rm adj}(B)} is the adjugate matrix which is the transpose of the cofactor matrix. Hence, the inverse of {(z I_n - A)} is given by

\displaystyle (z I_n - A)^{-1} = \frac M {\det (z I_n-A)} \ \ \ \ \ (7)

where

\displaystyle M= {{\rm adj} (z I_n-A)} ~. \ \ \ \ \ (8)

This adjugate matrix {M} contains entries that are polynomials in {z}. Hence, the entries of {M} are of finite degree in {z}. (In fact, due to the definition of the cofactor matrix they are of degree no larger than {n-1}.)

Next observe that the entries of {M} do not have negative powers of {z}. Hence, by the residue theorem, the entries {M_{ij}} of {M} satisfy

\displaystyle \frac 1 {2 \pi i } \oint M_{ij} ~dz =0 ~, \ \ \ \ \ (9)

because the complex residues at {z=0} all vanish.

The Cayley-Hamilton theorem now follows from (5), (7) and (9) :

\displaystyle \begin{array}{rcl} p(A) &=& \displaystyle \frac 1 {2 \pi i } \oint {p(z)} \frac M {\det (z I_n-A)} ~dz \\ &=& \displaystyle\frac 1 {2 \pi i } \oint M \frac {\det (z I_n-A) } {\det (z I_n-A)} ~dz \\ &=& \displaystyle \frac 1 {2 \pi i } \oint M ~dz =0 ~. \end{array}

\square

Appendix

There are several ways to prove (5). A common approach is to show convergence. Here I instead use formal power series, without worrying about convergence, since the latter can be checked a posteriori.

Taylor expanding {(1-x)^{-1}} we obtain the series

\displaystyle { 1 \over (1-x)} = \sum_{j=0}^\infty x^j ~.\ \ \ \ \ (10)

It should not therefore be a surprise that

\displaystyle { I_n \over (I_n-A)} = \sum_{j=0}^\infty A^j ~. \ \ \ \ \ (11)

The proof of the above is simple:

\displaystyle (I_n -A) \sum_{j=0}^\infty A^j = I_n \sum_{j=0}^\infty A^j - \sum_{j=1}^\infty A^j = I_n A^0 = I_n \ \ \ \ \ (12)

If we now put {A/z} in place of {A} we get

\displaystyle { I_n \over (zI_n-A)} = \sum_{j=0}^\infty \frac{A^j}{z^{j+1}} ~. \ \ \ \ \ (13)

Now consider that

\displaystyle \frac 1 {2 \pi i} \oint {z^k \over (zI_n-A)} dz = \frac 1 {2 \pi i} \oint \sum_{j=0}^\infty \frac{A^{j}}{z^{j+1-k}} dz ~. \ \ \ \ \ (14)

By the residue theorem, this last expression contains nonzero contributions only when {j=k}. So we obtain

\displaystyle \frac 1 {2 \pi i} \oint \sum_{j=0}^\infty {z^k \over (zI_n-A)} dz = A^k \ \ \ \ \ (15)

Observe that we now have an expression that we can substitute for {A^k} in any series expansioin involving powers of {A}. We are ready to prove the claim (5).

Since {f} is entire, its Laurent series has vaninishing principal part. We can thus write

\displaystyle f(z) = \sum_{j=0}^\infty a_j z^j ~~, \ \ \ \ \ (16)

so that

\displaystyle f(A) = \sum_{j=0}^\infty a_j A^j ~~, \ \ \ \ \ (17)

Invoking (15) we arrive at the claim,

\displaystyle f(A) = \sum_{j=0}^\infty a_j \frac 1 {2 \pi i} \oint {z^j \over (zI_n-A)} dz = \frac 1 {2 \pi i} \oint {f(z) \over (zI_n-A)} dz ~. \ \ \ \ \ (18)

\square

Derivation of the Gibbs entropy formula from the Boltzmann entropy

There are many ways to arrive at the Gibbs entropy formula

S= -k_B \displaystyle \sum_{i} p_i \log p_i~,

which is actually identical, except for units, to the Shannon entropy formula. Here I document a relatively straightforward derivation of the formula which might be the easiest route to develop intuition for undergraduate students who already know the formula for the Boltzmann entropy,

S(E)= k_B \log \Omega(E)~,

where \Omega(E) is the effective number of configurations of an isolated system with total energy E. This derivation is not new of course, but I decided to write it up anyway because it is a particularly elegant argument and is not always given emphasis in the usual textbooks.

Let us start by considering some general statistical ensemble such that a state i has energy E_i and probability p_i=p(E_i) which is the same for all states with the same energy E_i. For fixed energy E_i we can assume, from the principle of equal a priori probabilities, which is valid in the microcanonical ensemble, that

p_i = \displaystyle \frac 1 {\Omega(E_i)}~.

Hence we obtain for the Boltzmann entropy

S(E_i)=k_B \log \Omega(E_i) = -k_B \log p_i~.

For our general ensemble, the mean entropy is given by the weighted average, over all possible states, of the Boltzmann entropy, according to

S= \langle S(E_i) \rangle _i = \sum_i p_i S(E_i) = \sum_i p_i (-k_B \log p_i)

from which we obtain the famous Gibbs formula for the Boltzmann-Gibbs entropy:

S = -k_B \displaystyle \sum_i p_i \log p_i~.

 

 

 

The false premise in Moore’s open question argument

Normative statements, such as “killing is bad” or “thou shalt not kill” do not follow logically from merely informative facts.  Normative statements are prescriptive, in the sense that they tell you what you should do.   In contrast, informative facts or descriptive statements, also known as positive facts, merely describe a situation without offering a prescription about what to do.  For instance, the statement “people usually dislike being killed”, taken at face value, is not prescriptive (or normative), but rather simply a description of something that people dislike.  It has been known since the time of David Hume that there is a “gap” when one attempts to logically deduce a normative fact from a merely descriptive fact. In the above example, no amount of logical acrobatics will get you from the premise “people usually dislike being killed”  to the conclusion “thou shalt not kill.” This is the famous is-ought problem posed by David Hume, also known as Hume’s guillotine.

When I was in school, my father gave me a paperback with selected texts on philosophy, which included some by Hume.  I was mesmerized by the discussions concerning empirical knowledge.   Of all of the ideas and contributions that can be traced back to Hume, one idea has kept torturing me over many years: the dualism of facts and decisions implied by Hume’s guillotine.    This dualism in principle prevents us from deriving normative statements — hence ethics — using the scientific method, because the latter deals only with descriptive statements (see below).

Years later, in my 30s, I eagerly read  Karl Popper, who no doubt borrowed many of his ideas from Hume. For instance, according to Popper,  there is no certain empirical knowledge. All certain knowledge must be a priori and all empirical knowledge is tinged with uncertainty.   In The Open Societies and its Enemies, Popper explains very clearly that any descriptive fact can be used to argue a decision in both ways.  For example, if the fact of an almighty god’s existence could be somehow scientifically proven, this fact does not automatically imply that we ought to follow this god.   We could instead try to argue that this god must be dethroned.   Similarly, if a medicine fails to have a positive effect on a patient, one could argue that the medicine should be stopped. But one could also argue that we should double or triple the dosage.   Hume’s guillotine cuts both ways.

If you assume that Hume’s guillotine is a valid way of reasoning, then there are limits to how much the scientific method can be used to improve our decision making.   This limitation is due to how science essentially generates facts, whereas to make a decision one requires a value.  Science is, in this view, essentially anormative or amoral.

I thus read with great interest some recent texts by Sam Harris in which he argues that Hume’s guillotine is, after all is said and done, a mistake!  I was, to say the least, quite shocked.  Harris does not address the philosophical literature and others have pointed out that he essentially ignores centuries of philosophical thought in simply dismissing Hume’s guillotine.

But I still asked myself: could Hume’s guillotine be a mistake after all?

In this context, I decided to revisit one of the main pillars that support Hume’s guillotine, which is known as the open question argument, originally due to G. E. Moore in 1903. Moore argues logically that “good”  cannot be a natural property, for the following reason:

Premise 1: If a natural property X is identical to “good”, then the question “Is X identical to good?”  is a meaningless tautology.

Premise 2: The question “Is X identical to good?” is not meaningless and is a genuinely meaningful “open question”.

We thus get a contradiction. Hence, X cannot be identical to “good”.

The open question argument makes it very difficult to try to define “good” in naturalistic terms.   This is turn makes it very difficult to address “good” and “bad”  using the scientific method. (A notable exception is the “science” of medicine, where disease is unquestionably seen as bad and recovery is considered good.)

Below, I argue that Premise 1 is wrong.  The points raised here are not new, however, the particular example that I give  below probably has never been used in the context of the open question argument.

Consider the following question:

Is the number 1 identical to  \sqrt[3]{8 + 3 \sqrt{21}} + \sqrt[3]{8 - 3 \sqrt{21}} ?

To most readers, the answer to this question is not at all obvious.  Hence,  there is no sense in which this question is meaningless.   Moreover, the question is a simple binary yes/no question with a clear answer, but this answer is not immediately clear unless one tries to solve the maths.

It turns out that the answer to this question is YES, which means that we have a tautology:

1=\sqrt[3]{8 + 3 \sqrt{21}} + \sqrt[3]{8 - 3 \sqrt{21}}   .

Premise 1 of the open question argument assumes that tautological questions are meaningless, but we have already seen that this particular tautological question is not meaningless.

The above example has convinced me that the open question argument is based on a false premise and is therefore not valid.

More and more, I have become convinced that Hume (and Popper and Moore etc.) were wrong.   Perhaps  facts are not so ethically (and aesthetically) neutral after all.  The example of medicine comes to mind. If medicine can use the scientific method to improve our physical and mental health, I don’t see how it is logically possible for ethics to remain beyond the reach of the scientific method.

Many years before, I came across the same sentiment in the writings of Abraham Maslow, who also greatly influenced me (I remember how exciting it was for me to first read his list of B-values).  Now,  after reading Sam Harris, I am more than ever convinced that the scientific method will still deliver many new and priceless jewels of knowledge.

Given the recent populist wave in politics that seeks to discredit science, such views may thus come as a surprise, or at least as overly optimistic and naïve.   But I stand by my views.

I believe that we are at the dawn of an exciting new era where science will contribute significantly towards improving the moral and ethical dimensions of human social life and of our interactions with the environment.


I thank Marcos G. E. da Luz for the  mathematical example involving cube roots. I thank Helcio Felippe Jr. for discussions and feedback.

Random Search Wired Into Animals May Help Them Hunt

[ The link below takes you to an excellent article by Liam Drew in Quanta Magazine that discusses some of my work.  -Gandhi ]


A wide variety of predatory and foraging creatures may have evolved to follow a certain kind of random path — a Lévy walk — when no clues to the whereabouts of their food are available.

 

 

Nature endorses Joe Biden for US president

[ Source: https://www.nature.com/articles/d41586-020-02852-x ]


Why Nature supports Joe Biden for US president
We cannot stand by and let science be undermined. Joe Biden’s trust in truth, evidence, science and democracy make him the only choice in the US election.

On 9 November 2016, the world awoke to an unexpected result: Donald Trump had been elected president of the United States.

This journal did not hide its disappointment. But, Nature observed, US democracy was designed with safeguards intended to protect against excesses. It is founded on a system of checks and balances that makes it difficult for a president to exercise absolute power. We were hopeful that this would help to curb the damage that might result from Trump’s disregard for evidence and the truth, disrespect for those he disagrees with and toxic attitude towards women.

How wrong we turned out to be.

No US president in recent history has so relentlessly attacked and undermined so many valuable institutions, from science agencies to the media, the courts, the Department of Justice — and even the electoral system. Trump claims to put ‘America First’. But in his response to the pandemic, Trump has put himself first, not America.

His administration has picked fights with the country’s long-standing friends and allies, and walked away from crucial international scientific and environmental agreements and organizations: notably, the 2015 Paris climate accord; the Iran nuclear deal; the United Nations’ science and education agency UNESCO; and even, unthinkable in the middle of a pandemic, the World Health Organization (WHO).

Challenges such as ending the COVID-19 pandemic, tackling global warming and halting the proliferation and threat of nuclear weapons are global, and urgent. They will not be overcome without the collective efforts of the nation states and international institutions that the Trump administration has sought to undermine.

On the domestic front, one of this administration’s most dangerous legacies will be its shameful record of interference in health and science agencies — thus undermining public trust in the very institutions that are essential to keeping people safe.

Joe Biden, Trump’s opponent in next month’s presidential election, is the nation’s best hope to begin to repair this damage to science and the truth — by virtue of his policies and his leadership record in office, as a former vice-president and as a senator.

Four years ago, some hoped that Trump’s excesses would be reined in by his conservative Republican party, which has long valued the rule of law. Previous Republican presidents have also ascribed to a bipartisan tradition of supporting funding for science and innovation. But Trump has sought to remake the Republican party according to his own populist values.

Populists, from all points on the political compass, are on the rise around the world. They divide the world into ‘people’ and ‘elites’. The latter, according to populists, include researchers and the institutions where they work. The Trump administration has undermined trust in their knowledge, interfered with their autonomy, and expressed disdain for the essential role they have in national life. Supreme Court justices, civil-service professionals and journalists have been similarly attacked.
Coronavirus catastrophe

The Trump administration’s disregard for rules, government, science, institutions of democracy and, ultimately, facts and the truth have been on full display in its disastrous response to the COVID-19 pandemic.

In the pandemic’s earliest days, Trump chose not to craft a comprehensive national strategy to increase testing and contact tracing, and to bolster public-health facilities. Instead, he flouted and publicly derided the science-based health guidelines set by the US Centers for Disease Control and Prevention (CDC) for the use of face masks and social distancing.

The administration later rewrote guidelines when the message did not align with its agenda. Trump has lied about the dangers posed by the virus and has encouraged people to protest against policies intended to slow its transmission. The result, if not the goal, has been to downplay the greatest crisis the country — and the world — has faced in at least half a century.

These actions have had devastating consequences. With the nation’s death toll now exceeding 215,000, the coronavirus has killed more people in the United States than anywhere else. Even adjusting for population size, the country has fared spectacularly badly. Despite having vast scientific and monetary resources at his disposal, Trump failed catastrophically when it mattered most.

This undermining of research advice has been accompanied by the systematic dismantling of scientific capacity in regulatory science agencies.

The US Environmental Protection Agency (EPA), which was created 50 years ago under a Republican president, Richard Nixon, has helped many nations to better understand the dangers of pollution, and has pioneered regulations that have cleaned up the environment and saved millions of lives. But under the Trump administration, the EPA has withered as its scientists have been ignored by the senior leadership. Those at the top of the agency have worked to roll back or weaken more than 80 rules and regulations controlling a spectrum of pollutants, from greenhouse gases to mercury and sulfur dioxide.

Likewise, the CDC, which should have led the coronavirus response, was quickly made subordinate to a task force whose leaders include vice-president Mike Pence and Trump’s son-in-law, Jared Kushner — neither of whom has expertise in infectious diseases. Then, in July, the administration took away the CDC’s responsibility for coronavirus data collection, management and sharing, and handed this to the Department of Health and Human Services — the CDC’s parent institution, whose head, Alex Azar, is answerable to the president.

No president in recent history has tried to politicize government agencies and purge them of scientific expertise on the scale undertaken by this one. The Trump administration’s actions are accelerating climate change, razing wilderness, fouling air and killing more wildlife — as well as people.

Trump has also promoted nationalism, isolationism and xenophobia — including tacitly supporting white-supremacist groups. The administration has rewritten immigration policies, beginning in 2017 with a controversial travel ban on people from seven countries, including five Muslim-majority states. Even now, with the election weeks away, the Department of Homeland Security is proposing to limit the length of visas for international students.

The United States’ reputation as an open and welcoming country to the world’s students and researchers has suffered. International talent has clearly played a crucial part in helping the country to become a research and innovation powerhouse. Trump’s efforts to close borders, limit immigration and discourage international scientific cooperation — especially with researchers from China — are precisely the opposite of what is needed if the world is to succeed in tackling the mounting global challenges before us.
Biden must lead

Trump has not grown into his position as president, and has demonstrated that he can neither lead nor unite the United States.

Joe Biden, by contrast, has a history in the Senate as a politician who has reached across to his political opponents and worked with them to achieve bipartisan support for legislation — a skill that will be needed now more than at any time in the recent past, because he will inherit a nation that is even more divided than it was four years ago.

He has shown that he respects the values of research, and has vowed to work to restore the United States’ fractured global relationships. For these reasons, Nature is endorsing Biden and urging voters to cast a ballot for him on 3 November.

Biden’s campaign has worked closely with researchers to develop comprehensive plans on COVID-19 and climate change. He has pledged that decisions on the pandemic response will be made by public-health professionals and not by politicians; and he is rightly committing to restoring the ability of these professionals to communicate directly with the public.

In addition, Biden is promising to ramp up test-and-trace programmes and to provide more support for people hit hardest by the coronavirus. Combined with vaccines and medicines, these are the kinds of policies that will be essential to ending the pandemic.

On climate change, Biden would return the United States to the Paris agreement, and is proposing the most ambitious domestic climate policies ever advocated by nominees from the country’s major parties. A US$2-trillion plan would invest in clean energy and low-carbon infrastructure, with the ambition of weaning the United States off fossil-fuel-generated electricity by 2035.

If elected, Biden would have the chance to reinstate and strengthen the climate and environmental regulations rolled back under Trump; restore the EPA’s depleted scientific capacity; and return the CDC’s leadership role in the pandemic. He should also move to reverse egregious policies on immigration and student visas, and hold the United States to its international commitments — not least its membership of the WHO and UNESCO.

Donald Trump has taken an axe to a system that was intended to safeguard and protect citizens when leaders go astray. He has become an icon for those who seek to sow hatred and division, not only in the United States, but in other countries, too.

Joe Biden must be given an opportunity to restore trust in truth, in evidence, in science and in other institutions of democracy, heal a divided nation, and begin the urgent task of rebuilding the United States’ reputation in the world.

Nature 586, 335 (2020)


doi: https://doi.org/10.1038/d41586-020-02852-x