I am trying to solve the following problem : Let A be a square matrix whose entries are zeroes and ones. It is allowed to put minus ones instead of ones . Prove that this can be done in such a way that in every column and row the number of ones will differ from the number of minus ones at most by one . This problem is somehow related to Hamiltonian paths but I can't find the connection and I need help in finding that .

  • $\begingroup$ What if $A$ is an adjacency matrix for some graph $G$? $\endgroup$ – gt6989b Nov 4 '13 at 18:06

Lets start with a simple case:

(i) When the entries in the principal diagonal are zero.

$A$ is the adjacency matrix of a simple graph. We shall prove that every simple graph is orientable(by directing the edges appropriately) so that |outdegree-indegree|$\le 1$ for every vertex. This is equivalent to flipping 1's and -1's in the matrix and ensuring that the absolute value of every row sum and column sum is 1.

Note that the number of vertices with odd degree is even. Let $v_1,v_2,\dots ,v_{2k}$ be the vertices with odd degree. Draw new edges $v_iv_{i+1}\, \forall \, i\in \{1,3,\dots, 2k-1\}$. This new graph is eulerian because all vertices have even degree. Decompose the graph into edge-disjoint cycles, thereby orienting the graph such that outdegree equals to indegree of every vertex. Now remove those extra $k$ edges that were added. We must have |outdegree-indegree|$\le 1$ for every vertex.

(ii) When at least one of the entries of the principal diagonal is non-zero

Ignore the principal diagonal and proceed as in (i). Note that $i$th row sum is same as $i$th column sum ignoring the element $A_{ii}$. If

  • the row sum is 1, make $A_{ii}$ equal to -1.
  • the row sum is -1, make $A_{ii}$ equal to 1.
  • the row sum is zero, leave $A_{ii}$ undisturbed.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.