1
$\begingroup$

Let $G$ be a $d$-regular graph, and $A$ be the incidence matrix of $G$. Also suppose $B$ is a reduced echelon form of $A$ such that computations are in $\mathbb F_2$. Given matrix $B$, can we find matrix $A$?

If yes, how? and for arbitrary sparse matrix $A$ is this true?

And if no, can we use this method for constructing hash function?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Assuming you mean the vertex-edge incidence matrix, your row-echelon form determines the cut-space of the graph. Hence it is is determined by the natural graphic matroid. If the graph is 3-connected, this matroid determines the graph. Otherwise it does not - look up "Whitney flip".

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .