5
$\begingroup$

Let matrix $M \in \mathbb{N}^{5 \times 5}$ be symmetric with non-negative integer entries and zeros on the main diagonal and having the property that the row sums are equal to $2r$ for some $r \geq 2$. I want to prove that $M$ can be written as a non-negative integral linear combination of $5 \times 5$ symmetric matrices having non-negative integer entries with zero entries on the main diagonal and having the property that the row sums are equal to $2$. Is there way to prove this?

I tried with some simple examples and it seems to be correct.

$\endgroup$
  • $\begingroup$ I need to prove that any $M$ (with the property listed) can be written as a non-negative integral linear combination of matrices with the property listed. $m$ is not specific here. $\endgroup$ – jack Sep 21 at 9:28
  • $\begingroup$ I imagine this result is true for all dimensions, not just 5. $\endgroup$ – S. Dolan Sep 21 at 17:00
0
$\begingroup$

IDEA:

The row sums of $M$ are even, so there is either 0 or 2 or 4 odd numbers, and the diagonal entries are all zeros.

So if you have even entries, for example if you have that in $M$ the entries $m_{1,5}=m_{5,1}= 8$ then you will have in your linear combination $4$ multiplied by a matrix having all its entries on these rows are $0$ except $a_{1,5}=a_{5,1}=2$, and so on ...

Also if there is $2$ odd entries, for example $m_{1,5}=m_{5,1}=5$ and $m_{1,4}=m_{4,1}=7$, then in your linear combination you'll have $2$ multiplied by a matrix having $a_{1,5}=a_{5,1}=2$ and all other entries on these rows are zeros, and $3$ multiplied by a matrix having $b_{1,4}=b_{4,1}=2$ and all other entries on these rows are zeros, and a matrix having $c_{1,4}=c_{4,1}=c_{1,5}=c_{5,1}=1$ and all other entries on these rows are zeros, and so on...

I hope you can reach a proof from this hint and I am sorry because I am not able to write the whole proof now.

$\endgroup$
0
$\begingroup$

Yes, this conjecture is correct.

First consider the following matrices.

$X_1=\begin{pmatrix}0&0&1&1&0 \\0&0&1&0&1\\1&1&0&0&0\\1&0&0&0&1\\0&1&0&1&0\\\end{pmatrix}$, $X_2=\begin{pmatrix}0&0&1&0&1 \\0&0&1&1&0\\1&1&0&0&0\\0&1&0&0&1\\1&0&0&1&0\\\end{pmatrix}$, $X_3=\begin{pmatrix}0&0&1&0&1 \\0&0&0&2&0\\1&0&0&0&1\\0&2&0&0&0\\1&0&1&0&0\\\end{pmatrix}.$

If we could subtract one of the $X_i$ from $M$ without making any entry negative, then we would leave a matrix of the same type as $M$ but with $r$ reduced by 1. This process would therefore reduce $M$ to zero as we require.

If all off-diagonal entries of $M$ were non-zero we could subtract $X_1$. So, without loss of generality, we can suppose that $M_{12}=0$.

CASE 1. If no row of $M$ has three or more zeroes.

Without loss of generality we can suppose that $M$ has the following form where $A,B,C,D,E,F$ are all non-zero.

$M=\begin{pmatrix}0&0&A&B&C \\0&0&D&E&F\\A&D&0&.&.\\B&E&.&0&.\\C&F&.&.&0\\\end{pmatrix}$

If any of the dots were non-zero then a matrix like $X_1$ can be subtracted from $M$. Otherwise, all the dots are zero. Then $$A+D=B+E=C+F=2r. (*)$$ However, we would then have the sum of the first two rows equal to $6r$, a contradiction.

CASE 2. If a row of $M$ has four zeroes.

Without loss of generality we can suppose that $M$ has the following form.

$M=\begin{pmatrix}0&0&0&0&2r \\0&0&A&B&0\\0&A&0&C&0\\0&B&C&0&0\\2r&0&0&0&0\\\end{pmatrix}$

Then simple algebra shows that $A=B=C=r$ and $M$ is the sum of $r$ copies of $\frac {1}{r} M$.

CASE 3. If $M$ has three zeroes in a row but that no row has four or more zeroes.

Let $M=\begin{pmatrix}0&0&.&.&. \\0&0&.&.&.\\.&.&0&F&G\\.&.&F&0&H\\.&.&G&H&0\\\end{pmatrix}$

CASE 3(a). If $F=G=H=0$

Then the method used for $(*)$ gives a contradiction.

CASE 3(b). If two of $F,G,H$ are $0$, w.l.g. $F=G=0$

Then either $X_1$ or $X_2$ can be subtracted.

CASE 3(c). If only one of $F,G,H$ is $0$, w.l.g $F=0$.

Since every row has at least two non-zero elements, the possibilities for $M$ are, without loss of generality, as follows, where $+$ indicates a positive element.

$\begin{pmatrix}0&0&+&0&+ \\0&0&0&+&+\\+&0&0&0&G\\0&+&0&0&H\\+&+&G&H&0\\\end{pmatrix}$ and $\begin{pmatrix}0&0&+&.&. \\0&0&+&.&.\\+&+&0&0&G\\.&.&0&0&H\\.&.&G&H&0\\\end{pmatrix}$

Considering row totals for Rows 3 and 4 of the LH matrix shows that $M_{42}>1$ and so $X_3$ can be subtracted. For the RH matrix, one of $X_1, X_2$ can be subtracted unless the matrix is $\begin{pmatrix}0&0&+&+&0 \\0&0&+&+&0\\+&+&0&0&G\\+&+&0&0&H\\0&0&G&H&0\\\end{pmatrix}$

Then the sum of elements in Rows 1 and 2 must equal the sum of elements in Rows 3 and 4. Therefore $G=H=0$, a contradiction.

CASE 3(d). If $F,G,H$ are all non-zero.

Then a matrix like either $X_1$ or $X_2$ can be subtracted since the top two rows contain at least 4 non-zero elements.

$\endgroup$
  • $\begingroup$ With hindsight, CASE 1 can be subsumed into CASE 3(a) to shorten this proof a little. $\endgroup$ – S. Dolan Sep 21 at 16:41
0
$\begingroup$

A graph theoretic proof

Consider $M$ to be the adjacency matrix for a graph $G$. Then $G$ is a graph with no loops and 5 vertices, each of degree $2r$. We are required to prove that:

$G$ contains one or more simple cycles (i.e. containing no repeated vertex) which include every point precisely once.

Since all vertices have even degree, each component of $G$ must have an Eulerian cycle and therefore each vertex of $G$ is in a simple cycle and at least one of these simple cycles has length at least 3.

We can suppose every vertex of $G$ is joined to more than one vertex.

Suppose on the contrary that vertex 1 was only joined to vertex 2. By the equality of degrees, vertices 1 and 2 then form a component of $G$. The points 3,4,5 of the other component must then be joined in pairs and $G$ has simple cycles (1,2) and (3,4,5).

We can suppose $G$ only has simple cycles of lengths 2 and 3

There is nothing to prove if $G$ has a simple cycle of length 5, so suppose $G$ has the cycle (1,2,3,4). If vertex 5 were connected to two adjacent points in this cycle, say vertices 1 and 2, then (1,5,2,3,4) would be a simple cycle. So we can suppose 5 is only joined to, say, 1 and 3. Then (1,5,3,4) and ((1,2,3,5) are cycles and so 2 and 4 are also only joined to 1 and 3. There are then $6r$ edges from vertices 2,4,5 to 1 and 3, contradicting the degrees of 1 and 3.

Now consider a cycle of length 3, say (1,2,3). If vertex 4 were joined to two of these points then we would have a cycle of length 4. So vertex 4 is joined to vertex 5 and, say, vertex 1. Vertex 5 also has to be joined to precisely one of 1,2,3. This must be the same vertex 1, otherwise we would obtain a simple cycle of length 5. Vertices 4 and 5 can only be joined by $1$ edge (and similarly vertices 2 and 3 are only joined by $1$ edge) otherwise we would have simple cycles (1,2,3) and (4,5). Therefore there are $4(2r-1)$ edges from vertices 2,3,4,5 to vertex 1. Then $8r-4=2r$, which is impossible.

$\endgroup$
  • $\begingroup$ I don't think I follow your 'We are required to prove that'. Perhaps you meant something like: $G$ contains a collection of simple cycles such that each vertex belongs to exactly one of these cycles. Is that right? $\endgroup$ – Fimpellizieri Sep 22 at 21:04
  • $\begingroup$ Yes, that is correct. $\endgroup$ – S. Dolan Sep 22 at 21:06
  • $\begingroup$ I think your answer would benefit from better writing. I think you are trying to handle cases here rather than actually going 'without loss of generality' and it makes parsing the answer confusing. $G$ can very trivially have a simple cycle of length $5$, but I guess you're dismissing it as the easiest case for which what we need to prove is basically handed to us on a platter. $\endgroup$ – Fimpellizieri Sep 22 at 21:18
  • $\begingroup$ If G has a simple cycle of length 5 then, by definition, G contains a simple cycle which include every point precisely once. $\endgroup$ – S. Dolan Sep 22 at 21:24
  • 1
    $\begingroup$ Yes, that is my point. It's not 'Without loss of generality, we can suppose $G$ has no simple cycle of length $5$' and it most definitely isn't 'By definition, $G$ has no simple cycle of length $5$'. It's just that when $G$ has a simple cycle of length $5$, there is nothing to prove, so this case is done. Your answer is tackling cases, but is structured and written as something else, which makes it harder to parse. $\endgroup$ – Fimpellizieri Sep 22 at 21:28
0
$\begingroup$

This is my take on the graph theoretic approach by S. Dolan. Credits go to him.


Let $M$ be the adjacency matrix of a graph $G$, so that $G$ is a graph on $5$ vertices with no loops and such that each vertex has degree $2r$.

Claim: It is enough to prove that $G$ contains a collection of simple cycles such that each vertex belongs to exactly one of these cycles.

Indeed, if $H$ is the $G$-subgraph that corresponds to this collection, then each vertex of $H$ has degree exactly $2$. We can thus take the adjacency matrix of $H$ as one of the matrices in our integral linear combination that adds up to $M$.

We are hence left with the same problem, except now the rows of $M$ add up to $2(r-1)$; equivalently, except the vertices of $G$ have degree $2(r-1)$. Induction then takes care of finding the other matrices in our integral linear combination.


Let $v_1,v_2,v_3,v_4$ and $v_5$ be the vertices of $G$. We will prove the claim by studying different cases.

Case $(1)$: $G$ has a vertex which is joined to only one other vertex.

Assume without loss of generality that $v_1$ is joined only to $v_2$. Since all vertices have equal degrees, $v_2$ must also be joined only to $v_1$.

This implies that if some $u$ in $\{v_3, v_4,v_5\}$ were also joined to only one other vertex $w$, we would have $w \in \{v_3, v_4,v_5\}\setminus\{u\}$. Equality of degrees would then require that the remaining vertex be joined to itself, in contradiction to $G$ having no loops. It follows that each of $\{v_3, v_4,v_5\}$ is connected to the other two.

The collection of simple cycles $\{(v_1,v_2), (v_3,v_4,v_5)\}$ satisfies the claim and handles this case.


Case $(2)$: Each vertex of $G$ is joined to at least two other vertices.

By Veblen's Theorem, $G$ can be written as the union of disjoint simple cycles. We break down into subcases.


$\qquad (2.1)$: $G$ has a simple cycle of length $5$.

In this case, the claim is obviously satisfied and there is nothing to prove.


$\qquad (2.2)$: $G$ has a simple cycle of length $4$.

Let $(v_1,v_2,v_3,v_4)$ be the simple cycle.


$\qquad\qquad(2.2.1)$: $v_5$ is joined to two vertices that are adjacent in the cycle.

If that were the case, then we could enlarge the simple cycle to have length $5$. This reduces the problem to case $(2.1)$, which we have already handled.


$\qquad\qquad(2.2.2)$: No two vertices adjacent in the cycle are both joined to $v_5$.

Without loss of generality, suppose $v_5$ were joined to vertices $v_1$ and $v_3$. Notice that $v_5$ cannot be joined to any other vertex.

If $v_2$ and $v_4$ weree joined, then we could take the simple cycle $(v_1,v_2,v_4,v_3,v_5)$, handled by case $(2.1)$.

If $v_2$ and $v_4$ were not joined, then each of $\{v_2, v_4,v_5\}$ would be joined only to $v_1$ and $v_3$. This would contradict each vertex having equal degree, and finishes this case.


$\qquad (2.3)$: $G$ has a simple cycle of length $3$.

Let $(v_1,v_2,v_3)$ be the simple cycle.


$\qquad\qquad(2.3.1)$: One of $\{v_4, v_5\}$ is joined to two vertices in the cycle.

If that were the case, then we could enlarge the simple cycle to have length $4$. This reduces the problem to case $(2.2)$, which we have already handled.


$\qquad\qquad(2.3.1)$: No two vertices in the cycle are both joined to one of $\{v_4, v_5\}$.

Without loss of generality, suppose $v_4$ were joined to vertices $v_1$ and $v_5$. Notice that $v_4$ cannot be joined to any other vertex.

If $v_5$ were joined to one of $\{v_2,v_3\}$, then we could enlarge the simple cycle to have length $5$, handled by case $(2.1)$. Indeed, if $v_5$ were joined to $v_2$ we would have the cycle $(v_1,v_3, v_2,v_5,v_4)$ and if $v_5$ were joined to $v_3$ we would have the cycle $(v_1,v_2,v_3,v_5,v_4)$.

Suppose instead that $v_5$ were joined only to $v_1$ and $v_4$.
If there were more than edge joining $v_4$ and $v_5$, the collection $\{(v_1,v_2,v_3),(v_4,v_5)\}$ satisfies the claim.
If there were more than edge joining $v_2$ and $v_3$, the collection $\{(v_1,v_4,v_5),(v_2,v_3)\}$ satisfies the claim.
If $v_4$ were joined to $v_5$ by a single edge and $v_2$ were also joined to $v_3$ by a single edge, then $v_1$ would have degree $4(2r - 1) > 2r$, which contradicts our hypotheses and concludes this case.


$\qquad (2.4)$: $G$ has no simple cycle of length $3$ or more.

We show that this case is impossible.

$G$ does not have loops, so in this case it would contain only cycles of length $2$. $G$ would then be bipartite: its vertices could be divided into two disjoint sets $U$ and $V$ such that every edge of $G$ joins a vertex in $U$ to a vertex in $V$. But $G$ has $5r$ edges and one of $\{U, V\}$ has at most two vertices. This contradicts each vertex having degree $2r$ and finishes the last case.

$\endgroup$

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.