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?



Reduced echelon form of sparce matrices and constructing hash function
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".


