Combinatorial Matrix Algorithms

Fall 1998

Other resources

New! Check out the web site for the translation between graphs and adjacency matrices. It has a graphical interface, and is very easy to use.
Also take a look at a undergrad computer-based graph theory course that also has graph manipulation software for Windows machines.


Instructor: Dr. Art Duval

Please feel free to come by my office any time during scheduled office hours. You are welcome to come at other times, but in that case you might want to make an appointment, just to make sure that I will be there then. You can make an appointment simply by talking to me before or after class, by calling me at my office or at home, or by sending e-mail.

You may also ask any questions directly via phone or e-mail. If I'm not in when you call, please leave a message on the voice-mail or answering machine with your name, number, and a good time for me to call you back. I will try to repond to your phone or e-mail message as soon as possible.

Textbook: Combinatorial Matrix Theory, Brualdi and Ryser, Chs. 1-3, 5.

We will study (0,1)-matrices and adjacency matrices of graphs, and their relations. The ultimate goal is to understand how certain symmetry conditions on graphs may be explored using corresponding algebraic conditions on the adjacency matrix, and its eigenvalues. We will also see how, conversely, graphs of matrices can be used to understand matrices.


You need to know, and be comfortable with, the basics of combinatorics, graph theory, and linear algebra (especially eigenvalues/eigenvectors), such as may be found in the standard undergraduate courses.


The course grade will be based entirely on homeworks. There will be an initial due date (spaced approximately weekly) for each set of problems, by which time some work (however partial) must be turned in for each problem. These will be returned as soon as possible with questions and comments, after which you may respond, revise, amend, and then resubmit the problem. Resubmitted solutions will again be returned with comments and may again be revised and resubmitted. No more than ten problems may be submitted or resubmitted in a single week.

You are welcome, encouraged even, to work with each other, but you must write your solutions yourself. You may also consult with me in person about any problem, before or after the initial due date, for feedback and suggestions, in addition to the formal submit/re-submit procedure.

Each problem will be graded A, B, C, or D. In order to get an A, your solution must be not only correct, but also clearly-written. Your course grade will be the average, among all the problems for the semester, of the highest grade you ultimately achieve on each problem.

Drop date:

The deadline for student-initiated drops with a W is Fri., 16 Oct. After this date, you can only drop with the Dean's approval, which is granted only under extenuating circumstances.

I hope everyone will complete the course successfully, but if you are having doubts about your progress, I will be happy to discuss your standing in the course to help you decide whether or not to drop. You are only allowed three enrollments in this course, so please exercise the drop option judiciously.