Posted by: lewallen | August 12, 2009

Linear algebra bleg

At the risk of embarrassing myself, here’s a linear algebra question that has turned up in a knot theory project I’m working on. The post might be embarrassing because the answer might be “obviously not,” and I just don’t have enough linear algebra intuition to see it. On the other hand, this would contradict some things which seem to make sense from a knot theory perspective.

Say we have an n\times n matrix A. We can assume throughout that A is invertible, though maybe it doesn’t matter. Its determinant has the expansion

\det(A)=\sum_{\sigma\in S_{n}}\text{sgn}(\sigma) A_{1,\sigma(1)}\cdots A_{n,\sigma(n)}

where S_{n} is the symmetric group on n objects. One nice way to think of this (which might help for the problem), is that a permutation \sigma corresponds to a “choice” of a column of A by each row of A (so row i chooses column \sigma(i)), amounting to a particular bijection between rows and columns. Then, in the summand corresponding to \sigma in the above expansion, we see the element of each row which lies in the column it chose. (I’ve just learned that this way of looking at the expansion is exactly how Kauffman came up with his states-sum model for the Alexander polynomial. Would anyone be interested in an intro-post on the Alexander polynomial?)

Now suppose we have a matrix whose entries are only 0’s and 1’s. Suppose, furthermore, that all non-zero summands in the above determinant expansion are +1, i.e., the corresponding permutation is even. Call such a matrix special. Then the set of bijections between rows and columns which contribute a non-zero amount to the expansion has cardinality the determinant; call this set S1. First question: how to characterize special matrices in some less convoluted way (this is a side-question, but if there were some nice geometric characterization, it might help with the other question).

Now, another set which has cardinality \det(A) is the set S2 of solutions to A(v) \equiv 0, where v is some vector in (\mathbb{R}/\mathbb{Z})^n. To see this, just consider A( [0,1)^n )—it contains exactly \det(A) integral lattice points, and their preimages under A are the solutions in question.

So, my big question: is there some natural bijection between S1 and S2, some way to go from a bijection between rows and columns, to a particular solution to the system of equations over \mathbb{R}/ \mathbb{Z}? As I said at the beginning, I’m not sure whether there should be. It seems to me that maybe one just has to sit down and explicitly translate from the algebraic to the geometric definition of determinant. But I told myself I would abandon this project until the end of the summer, so maybe someone else wants to have a go? I’d appreciate any insights! Another option is that maybe there is some kind of “affine” bijection: we can get from one permutation to another by transpositions, and maybe there is some corresponding way to go between solutions?

In a later post, maybe I’ll talk about the knot theory part of this. On one side we have binary-dihedral representations of a knot group, and on the other side we have Kauffman states, or spanning trees of a certain graph, if you like, which happen to generate both the Khovanov and knot Floer complexes. The “Alexander matrices” which show up are special, in the above sense, in the case of alternating knots.

Thanks for any help!



  1. My initial thought is to use the Gessel-Viennot interpretation of det A as counting non-intersecting lattice paths. This probably doesn’t work, but I will think about it some more.

    But I wanted to post and say that I would definitely appreciate an introductory post to Alexander polynomials. And for that matter, any introductory knot theory would be welcome (completely ignorant here!)

  2. In my experience with a related question of this type, there doesn’t seem to be a well-known one. The related question is the relationship between spanning trees of a graph and its critical group / sandpile group, since both are counted by the same determinant (the reduced Laplacian), the former “naturally” and the latter via the nullspace. There is a known bijection using the so-called burning algorithm, but I’ve been told it’s ugly.

  3. My first, and indeed only, thought, is as follows. I don’t believe that your description of S2 depends on A being special, does it? If not, perhaps we should consider a more general matrix made entirely of 1s and 0s, and then find some geometric set whose points have a natural sign, so that when counted with sign they match up to S2?

    What I mean is this. My intuition is that a bijection of the type you’re asking for probably has a generalization provided that the sets are correctly weighted. For the set of permutations, the weighting is obvious. For the other set, not so much.

  4. “Would anyone be interested in an intro-post on the Alexander polynomial”

    That would be good!

  5. Thanks everyone for their responses! Qiaochu, that’s actually very interesting! It seems that the “non-naturality” of this burning algorithm lies somehow in a choice of edge-ordering, which is exactly (one of the) extra structures that comes up on the spanning tree side in knot theory. This stuff seems to be related, so I’ll look into it more.

    @Steven, I looked at this Gessel-Viennot stuff, at the very least it’s really cool! And I’ll try to send an Alexander poly. post up soon enough. Maybe I’ll also talk about going from Hopf algebras to knot invariants, since you taked about Hopfy type stuff at some point.

    Theo– this seems like the right way to go about things, but as far as I’ve been able to see, is just as hard as the original problem.

    Thinking about this again, I’ve realized/am convinced that there IS an answer, based on the knot theory. See in that case, there’s more structure: the set corresponding to “bijections,” has a fixed “0” element, and there’s a certain involution which only fixes that 0 element. Similar structure exists on the other side, even in the matrix case (0 element: trivial solution, involution: send each solution to 1 – that solution). But MAYBE there’s extra structured needed to get a bijection, which the knot theory provides.

    I want to spill the beans on the knot side ASAP, there’s some serious combinatorial structure here I think. But I wasn’t going to think about this anymore…! It’s fun though.

  6. Greg Kuperberg’s article:
    An exploration of the permanent-determinant method

    might be helpful. Kasteleyn’s method is also related to Gessel-Viennot.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: