Use of Netwon’s Method to Determine Matrix Eigenvalues

The problem here is to develop a routine that will determine one or more eigenvalues of a matrix using Newton’s method and considering the eigenvalue problem to be that of a nonlinear equation solution problem.

The simplest way to illustrate the problem and its solution is to use a 4 \times4 matrix.

Let us consider a square matrix A. The definition of an eigenvalue requires that

Ax=\lambda x

For our test case writing out the solutions for the left and right hand sides yields

\left[\begin{array}{c}  a_{{1,1}}x_{{1}}+a_{{1,2}}x_{{2}}+a_{{1,3}}x_{{3}}+a_{{1,4}}x_{{4}}\\  a_{{2,1}}x_{{1}}+a_{{2,2}}x_{{2}}+a_{{2,3}}x_{{3}}+a_{{2,4}}x_{{4}}\\  a_{{3,1}}x_{{1}}+a_{{3,2}}x_{{2}}+a_{{3,3}}x_{{3}}+a_{{3,4}}x_{{4}}\\  a_{{4,1}}x_{{1}}+a_{{4,2}}x_{{2}}+a_{{4,3}}x_{{3}}+a_{{4,4}}x_{{4}}  \end{array}\right]=\left[\begin{array}{c}  \lambda\, x_{{1}}\\  \lambda\, x_{{2}}\\  \lambda\, x_{{3}}\\  \lambda\, x_{{4}}  \end{array}\right]

The problem here is that, with the intrusion of the eigenvalue, we
have one more unknown than we have equations for. We can remedy this
by insisting that the values of x be normalized, or


Let us now construct a vector such that we have a closed system, all on the left hand side:

\left[\begin{array}{c}  a_{{1,1}}x_{{1}}+a_{{1,2}}x_{{2}}+a_{{1,3}}x_{{3}}+a_{{1,4}}x_{{4}}-\lambda\, x_{{1}}\\  a_{{2,1}}x_{{1}}+a_{{2,2}}x_{{2}}+a_{{2,3}}x_{{3}}+a_{{2,4}}x_{{4}}-\lambda\, x_{{2}}\\  a_{{3,1}}x_{{1}}+a_{{3,2}}x_{{2}}+a_{{3,3}}x_{{3}}+a_{{3,4}}x_{{4}}-\lambda\, x_{{3}}\\  a_{{4,1}}x_{{1}}+a_{{4,2}}x_{{2}}+a_{{4,3}}x_{{3}}+a_{{4,4}}x_{{4}}-\lambda\, x_{{4}}\\  {x_{{1}}}^{2}+{x_{{2}}}^{2}+{x_{{3}}}^{2}+{x_{{4}}}^{2}-1  \end{array}\right]=0

Since the object of Newton’s method is to arrive at this, we need an intermediate vector F, or

F=\left[\begin{array}{c}  a_{{1,1}}x_{{1}}+a_{{1,2}}x_{{2}}+a_{{1,3}}x_{{3}}+a_{{1,4}}x_{{4}}-\lambda\, x_{{1}}\\  a_{{2,1}}x_{{1}}+a_{{2,2}}x_{{2}}+a_{{2,3}}x_{{3}}+a_{{2,4}}x_{{4}}-\lambda\, x_{{2}}\\  a_{{3,1}}x_{{1}}+a_{{3,2}}x_{{2}}+a_{{3,3}}x_{{3}}+a_{{3,4}}x_{{4}}-\lambda\, x_{{3}}\\  a_{{4,1}}x_{{1}}+a_{{4,2}}x_{{2}}+a_{{4,3}}x_{{3}}+a_{{4,4}}x_{{4}}-\lambda\, x_{{4}}\\  {x_{{1}}}^{2}+{x_{{2}}}^{2}+{x_{{3}}}^{2}+{x_{{4}}}^{2}-1  \end{array}\right]

Let us make \lambda the last “x” or


The Jacobian of this vector with respect to the expanded x vector is

J\left(F,x\right)=\left[\begin{array}{ccccc}  a_{{1,1}}-\lambda & a_{{1,2}} & a_{{1,3}} & a_{{1,4}} & -x_{{1}}\\  \noalign{\medskip}a_{{2,1}} & a_{{2,2}}-\lambda & a_{{2,3}} & a_{{2,4}} & -x_{{2}}\\  \noalign{\medskip}a_{{3,1}} & a_{{3,2}} & a_{{3,3}}-\lambda & a_{{3,4}} & -x_{{3}}\\  \noalign{\medskip}a_{{4,1}} & a_{{4,2}} & a_{{4,3}} & a_{{4,4}}-\lambda & -x_{{4}}\\  \noalign{\medskip}2\, x_{{1}} & 2\, x_{{2}} & 2\, x_{{3}} & 2\, x_{{4}} & 0  \end{array}\right]

Now we can solve the Newton’s method equation iteratively:


It is certainly possible to invert the Jacobian symbolically, but the algebra becomes very complicated, even for a relatively small matrix such as this one. A more sensible solution is to obtain numerical values for both Jacobian and F vector, invert the former using the Gauss-Jordan technique and then multiply this by the F vector before performing the Newton iteration.

Now let us consider the case of the tridiagonal matrix

A=\left[\begin{array}{cccc}  2 & -1 & 0 & 0\\  \noalign{\medskip}-1 & 2 & -1 & 0\\  \noalign{\medskip}0 & -1 & 2 & -1\\  \noalign{\medskip}0 & 0 & -1 & 2  \end{array}\right]

The eigenvalues of this matrix are


or numerically 3.618033989, 1.381966011, 2.618033989, and .381966011. The FORTRAN 77 code used for this is given at the end of the problem. Although the matrix is “hard coded” into the program, it is only necessary to change one parameter to change the matrix size.

The summary results of Newton’s Method are shown below.


There are two different quantities tracked above:

  • The residual, i.e., the Euclidean norm of the entire x vector.
  • The error, i.e., the change in the eigenvalue from one step to the next.

Both these are tracked for three different starting places. For convenience,
all of the x vector entries were initialized at the same value.

Some comments on the solution are as follows:

  • As mentioned earlier, there were four eigenvalues to be determined. The method only returns one eigenvalue for each starting point, and that eigenvalue depends upon the starting point. The eigenvalues determined were 0.381966 (Start = 1 and Start = 2) and 2.6180339 (Start = 3.) Like the power method, this solution determines both an eigenvalue and eigenvector. Unlike the power method, it does not necessarily return the largest and/or smallest eigenvalue or even one easily predictable by the choice of starting value. With Newton’s Method, this is unsurprising; with multiple roots of an equation, which root is found very much depends upon the starting point. However, in the case where the number of roots is (in simple terms) the basic size of the matrix, this correspondence can become very complicated, and in some cases it is possible that certain eigenvalues will be missed altogether.
  • As a corollary to the previous point, with some starting values the convergence almost comes apart, especially where Start = 3. With larger values than this, the program generates “nan” values and terminates abnormally. This result is a part of the method; poor initial estimates can led successive iterations “off the track” and thus fail to converge. Thus it is necessary to know the range of eigenvalues before one actually determines them, which to a great extent defeats the purpose of the method.
  • The method is better at finding eigenvalues than finding eigenvectors. The residuals of the vector (which include the eigenvector plus the eigenvalue) converge much more slowly than the error. Those runs that were not limited by the termination criterion of the eigenvalue (|\Delta\lambda|<1.0\times10^{-6}) showed a very slow convergence continue with the eigenvectors. For the eigenvectors, the convergence rate is reasonable.

The general impression of this method, therefore, is that under proper circumstances it is capable of producing eigenvalues and (to a lesser extent) eigenvectors, but that it is necessary to a) have some idea of the values of the eigenvectors going in and b) be prepared for the method to collapse with the wrong initial guesses. One possible application (given the convergence limitations discussed above) is to use it in conjunction with, say, the Householder-Givens Method to determine the eigenvectors, which do not come out as a result of this method. The known eigenvalues give excellent starting values.

These results are confirmed when we expand the matrix to 10\times10.


We see that all of the errors and residuals go up and down from the initial guesses until convergence was achieved. The eigenvalues determined were 0.6902785 (Start = 1,) 1.7153704 (Start = 2,) and 1.7153703 (Start = 3.) Thus as before with three initial starting values only two eigenvalues were determined. The convergence was more lengthy than with the smaller matrix but not by much. This means that the method may be, to some extent, insensitive to matrix size, which would make it useful with larger matrices.


The code calls several “standard” routines and includes whose significance is as follows:

  • matsize.for is an include which includes a parameter statement for the actual matrix size. For the 10\times10 matrix, it read as follows:
    • parameter (nn=10, nplus1=nn+1,mcycle=100)
  • xmtinv is a subroutine to invert a matrix using Gauss-Jordan elimination.
  • matvec performs matrix-vector multiplication (in that order).
  • veclen computes the Euclidean norm of a vector.
 c Determination of Eigenvalue(s) of Tridiagonal Matrix using
 c Newton's Method
 include 'matsize.for'
 dimension a(nn,nn),x(nplus1),f(nplus1),fj(nplus1,nplus1),
 call tstamp
 c Define original matrix a
 do 1 i=1,nn,1
 do 1 j=1,nn,1
 if (i.eq.j) a(i,j) = 2.0
 if (abs(i-j).eq.1) a(i,j) = -1.0
 1 continue
 open (unit=2,file='m5610p2d.csv')
 write(2,*)'Original Matrix'
 do 2 i=1,nn,1
 2 write(2,3)(a(i,j),j=1,nn,1)
 3 format(100(g10.3,1h,))
 c Make initial guesses of eigenvalues and values of x
 do 100 mm=1,3,1
 write(2,*)'Eigenvalue Results for vstart =',vstart
 do 4 i=1,nplus1,1
 4 x(i)=vstart
 c Cycle Newton's method
 do 5 m=1,mcycle,1
 c Compute Jacobian for current step
 do 6 i=1,nplus1,1
 do 6 j=1,nplus1,1
 if(i.eq.nplus1.and.j.eq.nplus1) then
 goto 6
 if(i.eq.j) then
 goto 6
 if(j.eq.nplus1) then
 goto 6
 if(i.eq.nplus1) then
 goto 6
 6 continue
 c Output Jacobian
 write(2,*)'Jacobian Matrix'
 do 10 i=1,nplus1,1
 10 write(2,3)(fj(i,j),j=1,nplus1,1)
 c Compute Newton "F" vector
 do 20 i=1,nplus1,1
 21 f(i)=-x(nplus1)*x(i)
 do 23 j=1,nn,1
 23 continue
 goto 20
 22 f(i)=-1.0
 do 24 j=1,nn,1
 24 f(i)=f(i)+x(i)**2
 20 continue
 c Invert Jacobian
 call xmtinv(fj,nplus1,nplus1)
 c Postmultiply Jacobian by f vector
 call matvec(fj,f,xt,nplus1,nplus1)
 c Update Value of x vector and output the result
 write(2,*)'Result Vector for m = ',m
 do 7 k=1,nplus1,1
 7 write(2,*)x(k)
 c Compute norm of residual and error
 call veclen(xt,resid(m),nplus1)
 if(resid(m).lt.1.0e-07.or.eigerr(m).lt.1.0e-07)goto 30
 5 continue
 c Output residual plot
 30 write(2,*)'Residuals and Errors'
 101 format(27hIteration,Residual (Start =,i2,
 &16h),Error (Start = ,i2,1h))
 do 31 i=1,m-1,1
 31 write(2,32)i,resid(i),eigerr(i)
 32 format(i3,2(1h,,g10.3))
 100 continue

Rev. Ian Mitchell: The American Folk Song Mass

(FEL 7401-M) 1967

The 1960’s were a time of ferment and change in the U.S., and, then as now, institutions had a hard time keeping up with them, let along getting ahead.

One attempt to do so was The American Folk Song Mass, performed by the Canterbury Choir at Northwestern University under the direction of Rev. Ian Mitchell.  Unlike many of its Catholic counterparts, it’s not trying to define a new style in liturgical celebration but to import in an Aaron Copelandish kind of way existing folk styles of the country.  To this end the music he uses folk styles from various traditions, mixed with the 1928 Book of Common Prayer liturgy and his own monologues (another common feature of 1960’s Catholic and Episcopal folk music).

A fair comparison is The Winds of God.  In some ways Mitchell was ahead of his California counterparts in breaking from the musical tradition of his own church.  On the other hand, Gere boiled his explanatory monologue to one place in the work; Mitchell gets a little verbose, which breaks the flow of the album.

Mitchell’s monologues, however, highlight his social activism, which was a part of his ministry.  He was in the Chicago tradition of activist priests and ministers, which included his contemporary Peter Scholtes (more adventurous in his own musical efforts) and of course Jeremiah Wright, whose influence on all of us has yet to be properly assessed.  (Mitchell went on to produce a Catholic version of this album.)

His use of different forms of American folk music was of a piece with his social activism, something from the people.  His use of Appalachian Scots-Irish style music may have been a miscalculation, given the fact that these people have been at the vanguard of the pushback against the kind of social activism that Mitchell espoused.  Although, as was the case with The Winds of God and other contemporary efforts, events and styles were moving in a different direction, it’s a reasonable attempt at meeting a rapidly changing world at least halfway.

The songs:

  1. Introduction To The Mass
  2. Lord, Have Mercy Upon Us
  3. Introduction to The Nicene Creed
  4. I Believe In One God
  5. The Elements Of The Eucharist
  6. Lift Up Your Hearts – Holy, Holy, Holy
  7. The Lord’s Prayer
  8. The Priesthood of Christ
  9. O Lamb of God
  10. The Communion
  11. Glory Be To God On High
  12. The Close
  13. Jerusalem My Happy Home
  14. Alleluia Sing To Jesus
  15. A Home In That Rock
  16. Scarlet Ribbons

Download The American Folk Song Mass

Music Pages

The Fading Glory Problem Affects the Prediction of Hurricane Sandy

A few months ago I ran a piece entitled Fading Glory, where I made the following observation re the place where I’m working on my PhD in Computational Engineering:

One of the things my advisor oriented us about were the substantial computer capabilities that the SimCentre has.  “Substantial” is a relative term; at one point we were in the top 500 computers in the world for power, but he chronicled our falling ranking which eventually left us “off the charts”…What has happened to the SimCentre was not that the computer cluster there had deteriorated; it has just not kept up with the ever-larger supercomputers coming on-line out there.

That’s pretty much the cause of the success of the European model–and the failure of the American one–to predict Sandy’s landfall:

Forecast models require some serious computational horsepower, which can only be supplied by supercomputers. The ECMWF, for example, utilizes an IBM system capable of over 600 teraflops that ranks among the most powerful in the world, and it’s used specifically for medium-range models  That, fundamentally, is the reason their model frequently outperforms the American one. The US National Weather Service’s modeling center runs a diversity of short-, medium-, and long-term models, all on a much smaller supercomputer. The National Weather Service has to do more with less.

I’ve lamented the way we’ve allowed our transportation infrastructure to deteriorate, but that also applies to other parts of our infrastructure, which includes simulation (as opposed to the statistical extrapolations which are so popular).  At the root the United States, for all the blessings it has been endowed with, has a broad-based “fading glory” problem based on its dysfunctional political system, and that in turn is based on its dysfunctional society.

People in the business routinely talk about computational routines being “expensive” but in reality it’s nothing compared to the damage of an unexpected hurricane. Of course, we might have some more breathing room if we wouldn’t overdevelop our coastal areas, but that’s another post.

Math and the Middle East: Some Things Never Change

Every now and then you’ll hear a news item about someone’s math problem being controversial (involving slavery, etc.)  This gem has been around for a long time: it comes from Marvin Marcus’ A Survey of Finite Mathematics (Boston: Houghton Mifflin Company, 1969).  It’s purpose is to illustrate the use of combinatorial matrix theory, and (stripping away the technical details) goes like this:

Five hostile Middle Eastern countries have long-range weapons array with respect to each other as follows: each country has its weapons aimed at two different countries and is the target for the weapons of two different countries…if all the countries fire their weapons at once, is it certain that they will all be destroyed?

The matrix analysis he undertakes comes to the following conclusion:

Hence it is certain that if the countries start firing they will destroy one another in some order.

Some things never change…and there is no consideration to the collateral damage to the neighbouring countries.

The Christmas Story, from the Cofraternity Version

Now it came to pass in those days, that a decree went forth from Caesar Augustus that a census of the whole world should be taken.  This first census took place while Cyrinius was governor of Syria.  And all were going, each to his own town, to register.

And Joseph also went from Galilee out of the town of Nazareth into Judea to the town of David, which is called Bethlehem–because he was of the house and family of David–to register, together with Mary his espoused wife, who was with child.  And it came to pass while they were there, that the days for her to be delivered were fulfilled.  And she brought her firstborn son, and wrapped him in swaddling clothes, and laid him in a manger, because there was no room for them in the inn.

And there were shepherds in the same district living in the fields and keeping watch over their flock by night.  And behold, an angel of the Lord stood by them and the glory of God shone round about them, and they feared exceedingly.  And the angel said to them, “Do not be afraid, for behold, I bring you good news of great joy which shall be to all the people; for today in the town of David a Savior has been born to you, who is Christ the Lord.  And this shall be a sign to you: you will find an infant wrapped in swaddling clothes and lying in a manger”.  And suddenly there was with the angel a multitude of the heavenly host praising God and saying, “Glory to God in the highest, and on earth peace among men of good will”.

And it came to pass, when the angels had departed from them into heaven, that the shepherds were saying to one another, “Let us go over to Bethlehem and see this thing which has come to pass, which the Lord has made known t us”.  So they went with haste, and they found Mary and Joseph, and the babe lying in a manger.  And when they had seen, they understood what had been told them concerning this child.  And all who heard marvelled at the things told them by the shepherds.  But Mary kept in mind all of these things, pondering them in her heart.  And the shepherds returned, glorifying and praising God for all that they had heard and seen, even as it was spoken to them.  (Luke 2:1-20)

The Cofraternity New Testament (Cofraternity coming from the Cofraternity of Christian Doctrine or CCD, well-known to Roman Catholics) was produced in 1941.  It was a modernisation of the Douai-Rheims-Challoner New Testament translation which English-speaking Roman Catholics had used since before King James’ translation.  It remained the “modern” Roman Catholic English translation of the New Testament (there was, of course, Knox’ version) until 1964, and was ultimately superseded by the New American Bible in 1970.

It’s Hard to Admit When You’re Inferior, Especially When You Are

I am amused at the persistence of the New York Times editorial Asians–Too Smart for Their Own Good?

AT the end of this month, high school seniors will submit their college applications and begin waiting to hear where they will spend the next four years of their lives. More than they might realize, the outcome will depend on race. If you are Asian, your chances of getting into the most selective colleges and universities will almost certainly be lower than if you are white.

Asian-Americans constitute 5.6 percent of the nation’s population but 12 to 18 percent of the student body at Ivy League schools. But if judged on their merits — grades, test scores, academic honors and extracurricular activities — Asian-Americans are underrepresented at these schools. Consider that Asians make up anywhere from 40 to 70 percent of the student population at top public high schools like Stuyvesant and Bronx Science in New York City, Lowell in San Francisco and Thomas Jefferson in Alexandria, Va., where admissions are largely based on exams and grades.

If you stop and think about this, it’s a real eye-opener.

Our elites justify their dominance of the society based on their claim that we now have a “meritocracy” populated by people of superior intelligence.  The cornerstone of this is academic achievement.  Thus, a group of people who have high academic achievement should have pride of place in this system.  The under-representation of Asians in the “gateway” schools puts the lie to the paradigm.

So what do your élite institutions do to counteract this truth?  The same thing their Jim Crow predecessors did when faced with the same problem: they discriminate!  Most people look at racism in purely moral terms, but the driving force behind the whole unequal system in the South–first slavery, and then our own apartheid–was the realisation by the Scots-Irish that they faced in black people a group who had a greater capacity for work then they had.

But we must sugar-coat the process.  Part of it is the habit of Ivy League schools to favour those whose ancestors haunted the halls of ivy in their day.  But another is their obsessive fixation on “socialisation” types of issues.  They look for people who are “well-rounded” and capable of composing mellifluous prose on entrance applications which show their “noble aspirations” beyond the next drinking binge.  Since the Asians, by and large, concentrate on the academic achievement task in front of them, they’re at a disadvantage in a system like ours.

I am as alive as anyone of the limitations of the meaning of academic perfection.  But, after flaying the rest of the population with their ignorance and lack of formal education, to rig a system to keep out people who can eat their lunch academically–and probably after they graduate–can only be described as duplicitous.

In times past people started civil rights campaigns over stuff like this.  But we are a society harder to shame now than in the past, and the Asians for the most part aren’t inclined to such a course of action.  They, however, have their ascendant home countries (well, most of them) to offer them either a career after they graduate or connections to help the one they have here.

In either case, when Asia finally overtakes us, there will be tears shed.  But they won’t be mine.

The Africans, Emboldened by Options

For instance, the Chinese:

China is the largest financier on the entire continent. Chinese corporations, financial institutions, and the government have invested billions of dollars in large new dams, for example.

And why?

Indeed, many African governments prefer China as an economic partner over Western countries for a number of reasons. First, China’s own development experience has instructive value. Second, China fulfills Africa’s need for critical infrastructure more cheaply, less bureaucratically, and more quickly. And finally, China portrays Africa more positively as a partner in “mutually beneficial cooperation” and “common prosperity”, rather than a “doomed continent” requiring aid.

Anglicans, of course, know that Africa–especially just north of the Equator–is “home base” for orthodox Anglicanism in the world today.  There are many in the “First World” who would like to change that, and not only TEC but also, for example, the UK (and to a lesser extent the US) government, which has tied foreign aid to embrace of its idea of “equality”.

But the ability to act and think independently are intimately tied to economic independence, or at least the availability for options.  In a world that is become more “multipolar” by the day, more and more places have options that transcend the colonial constructs of the past, and that works on more than one level.

Now if we could just get them to move Canterbury…

Peter Giardina: Song of Solomon

Giardina-Pete-Song-Of-Solomon(Music Mountain MMP-PG-1001)  1975

Every now and then an album comes along which, at least in part, takes your breath away, and this is one of them.  It is skilfully done, laced with the mellotron, that 1960’s and 1970’s instrument that’s at once the product of technology and yet difficult to digitise, and profoundly spiritual.  Although all the tracks aren’t on the highest plane, when they are, they are.  His opening, the title track, gets off to a slow start, but then takes off.  “Dance Song,” his rendition of the old liberal favourite, is the best I know of.  And the closing, “One More Mile to Go”, is the absolute best “homecoming” song I know of.  Southern Gospel cannot touch it; only this comes close.

Although the album says it was made in Indiana, Pete Giardina is a son of the Gulf Coast.  His father was a New Orleans jazz musician and he was raised in the Dallas area.  He is still an active musician in the Dallas area.

The songs:

  1. Song Of Solomon
  2. Darkness Before The Dawn
  3. Never Alone
  4. Dance Song
  5. Christ Of Galilee
  6. Billows And Waves
  7. One More Mile To Go

Download Song of Solomon

See our Music Page

Daniel “What a Liar” Inouye Gone

The last of the Watergate Committee in the Senate passes:

Sen. Daniel K. Inouye of Hawaii, a highly decorated World War II combat veteran who used his status as one of the most powerful Democrats in Washington and the second-longest-serving senator in history to send billions of dollars to his home islands, died Monday at Walter Reed National Military Medical Center in Bethesda. He was 88.

His main claim to fame, IMHO, was this during the Watergate hearings:

Watched by millions of viewers on network television over the course of three months, the sessions introduced Sen. Inouye to the public as an undaunted questioner of top White House aides, including H.R. Haldeman and John D. Ehrlichman (right).

Ehrlichman’s sworn testimony prompted a rare moment of unguarded emotion from Sen. Inouye. “What a liar!” he whispered into a microphone he thought was off.

The next week, Ehrlichman’s attorney referred to Sen. Inouye as “that little Jap,” prompting a wave of thousands of telegrams and letters in support of the senator.

But you can hear it for yourself by clicking here and listening to that part of the hearings.

No More Time to Run: My Response to the Newtown, CT School Shootings

Events like the Newtown, CT school shootings simply leave one numb.  As one who moves in the halls of academia, the possibility of something like that happening is one that crosses the mind.  When it does take place, it hurts.

Not so far from Newtown is Danbury, CT.  Years ago a group of very accomplished musicians from there made an album entitled Outpouring, and podcasting its ending track No More Time to Run is my response, poor though it may be, to this tragedy.  It not only comes from the area but is right for the season as well.

My prayers are with the families and others who have come through this.