# A Combinatorial problem , matrix

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 .

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

## 1 Answer

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.