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.
Syllabus
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.
Prerequisites:
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.
Grades:
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.