# Teaching LU Factorization in a sophomore-level Linear Algebra course

I teach this course from David Lay's Linear Algebra and Its Applications, which on the whole is a great textbook and explains things well. It does not explain the steps of LU factorization well, so I started exploring online to see some other explanations. I noticed that most sources describe it only for square matrices. That would make an explanation of the steps much easier.

My question here is whether there is any need (in a sophomore level course) to include non-square matrices (in the LU factorization topic)?

• I agree that LU decomposition is not a high priority item. However, it can be obtained just by carefully keeping track of row reduction steps in the Gaussian elimination algorithm, together with an understanding of how to achieve row operations using matrix multiplication. It could be viewed as a nice "bonus" theorem, which is not a main goal of the course, but is just a "cool observation". Aug 8, 2021 at 16:12
• @StevenGubkin: Good point. The LU decomposition is also a first introduction to matrix factorizations. Later, students will see other factorizations, making use of additional concepts beyond Gaussian elimination, such as orthogonality, eigenvalues and eigenvectors.
– J W
Aug 8, 2021 at 16:30
• Yep. Diagonalization seems much more useful than LU decomposition. Every time I teach this course, I wish I were more knowledgeable in all the directions one can go from here. Aug 8, 2021 at 16:33
• @SueVanHattum: That might make a good question in its own right (regarding your remark on where to go from diagonalization).
– J W
Aug 8, 2021 at 16:43
• I meant it more as: What will my students be doing with all this, after this course? How do I connect the material I teach in this course to future courses? I don't feel like it's a question I can ask here. I feel like I could benefit from taking a whole bunch more higher level courses related to this. (But I most likely will not do that. I'm 64, and will retire in 5 or 6 more years. My dedication is to the planet, and I will keep teaching math because of the joy it brings me, but I won't likely learn a whole lot more math.) Aug 8, 2021 at 17:43

Poole's Linear Algebra: A Modern Introduction, 2nd edition, relegates the non-square case of the LU factorization to an exercise. Strang's Introduction to Linear Algebra, 5th edition, does square systems only for LU, unless I've missed something tucked away somewhere. When covering LU in a first linear algebra course, I think it's fine to keep to the square case for this topic. Non-square linear systems can receive more attention later in the course when covering linear independence, subspaces, dimension, rank and the like.

In a comment, you also wonder whether to skip LU entirely. I think it has a place as a first introduction to matrix factorizations. As Steven Gubkin writes, it uses only "row reduction steps in the Gaussian elimination algorithm, together with an understanding of how to achieve row operations using matrix multiplication." It can also be used as a springboard to numerical linear algebra, teaching the algorithms used to solve problems in practice alongside the theory, but as Ben Crowell points out, this could be delayed until a first course in numerical analysis. My concern here is that some students may never take such a course and should arguably be given some exposure to numerics.

This is just a data-point from my own background. I double-majored in math and physics as an undergrad and got my PhD in physics. I did a postdoc and then became a community college teacher for 25 years. I taught 98% physics and 2% math.

I'm pretty sure we never saw LU decomposition at all in my sophomore course at Berkeley. I think I learned it for the first time in an upper-division course. (I think we may have seen it both in upper-division linear algebra and in numerical analysis.) If you asked me today, I would not remember what it was for or how to do it, just that it's the name of some way of factoring a matrix. The fact that it can even be defined for a non-square matrix is a complete surprise to me.

Speaking purely as a physicist, we basically never use non-square matrices. The most frequent application is to operators in quantum mechanics, which are always maps from a given space back to the same space, so in the finite-dimensional case they're always square matrices. In fact, we usually only care about operators that are either unitary (for time-evolution) or Hermitian (for observables).

I don't know, maybe an economist, for example, would have a different point of view, but my impression is that doing LU factorization at all is kind of esoteric for a sophomore class, and the fact that it can be done for non-square matrices is super esoteric.

• Well, if "kind of esoteric" includes "rarely used in real life because it is too simplistic to be useful" your last sentence may be right. But most graduates don't seem to realize that that "numerical methods" even exist, judging by their attempts to write computer code. At best, they do things that were obsolete 50 years ago. At worst, they do things that don't even work at all except on toy problems. (Would you call singular value decomposition of rectangular matrices "too esoteric"? It's far more generally useful than LU decomposition!) Aug 8, 2021 at 12:27
• @alephzero: The success of the open source movement has brought high-quality numerical analysis software to the masses. If I have to solve a system of linear equations, I'm not going to implement my own version of an algorithm. My procedure would be to carefully characterize my problem (is the system sparse, etc.), then if it doesn't have any unusual characteristics I would just use the most generic subroutine from whatever package is handy. If it does have unusual characteristics, I'd look on Wikipedia to figure out what algorithm is most appropriate, then use that. To be able to do that ...
– user507
Aug 8, 2021 at 12:42
• @JW I was just thinking about skipping the LU decomposition for non-square matrices. But Ben's answer makes me wonder how valuable the whole topic is. Aug 8, 2021 at 16:29
• [...] of exposure to numerical analysis, but realistically this is what an upper-division numerical analysis class is for. I do remember as a college freshman working out for myself how to do reduce a least-squares fitting problem to a problem in linear algebra. But I'm extremely skeptical about the value of such a thing when it's part of a more general lower-division class and kids are just being marched through it as a series of algorithms to perform on a test. It's not the topic of the course, and almost none of them will retain any of it.
– user507
Aug 8, 2021 at 18:29
• FWIW, knowing similar processes to LU decomposition is very useful in pure math. At a base level a similar process proves the fundamental theorem of finitely generated abelian groups in graduate algebra courses (using Smith Normal Form which is very close to LU decomposition but in Z coefficients) .... but I'd call this an edge case. If your students will go on to pure math or combinatorics, they should absolutely be exposed to it. I can think of several other times where we simply proved something for matrices with one off-diagonal element and then generalized to all matrices. Aug 11, 2021 at 22:04