I am looking at directed acyclic multi-graphs $G=(V,E)$ with a single source and sink with integer labeled arcs. Each vertex has exactly two inputs except $s$. Each vertex has at least one output except $t$. So $|E|=2(|V|-1)$

Each one of these graphs represent an infinite number of addition chains that differ only in the number of doubling steps. I can use the arc-path incidence matrix to calculate what possible addition chains the graph encodes. These matrices seem to have a consistent set of properties that I expect are likely well known but I don't know what they would be called.

1) It always seems possible to do row reduction in the integers

2) The rank of the matrix always seems to equal the number of vertices

3) While the column space of the matrix seems complicated it's null space seems to always be represented by a basis with vectors containing two 1s, two -1s and the rest zero.

With property three is it often the case that the null space can seem simple in structure while the column space seems complicated? Presumably this can happen in reverse.

For a particular conjecture I am investigating I want to break down the column space of a matrix into sets of what I would call internal translations. So for example show vectors have the a format similar to:


Where $\alpha$ is a permutation of $1...z$.

The idea here is to show if certain column entries bunch together then others have to bunch as well. These internal translations are caused by having two different ways from getting from vertex to vertex. What would such a structure be called?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.