Making column sum of adjacency matrix even.
$begingroup$
Let $G$ be a connected graph with $V$ vertices and let say I have an adjacency matrix of order $N$, how can I make sum of each column even?
Like I have a graph with $4$ vertices and $4$ edges as
$begin{bmatrix}0 & 1 & 0 &0 \
0 & 0 & 1 & 0\
0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 end{bmatrix}$
And I want to convert it like this,
$begin{bmatrix}0 & 0 & 0 &0 \
1 & 0 & 1 & 0\
0 & 0 & 0 & 0\
1 & 0 & 1 & 0 end{bmatrix}$
For reference, if $i^{th}$ element of the $j^{th}$ row is $1$ then the edge is directed from $j$ to $i$.
You can reverse any edge between two vertices such that the graph remains connected. And the adjacency matrix's indexing starts from 1 rather than from 0.
matrices discrete-mathematics graph-theory matrix-equations
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
$endgroup$
add a comment |
$begingroup$
Let $G$ be a connected graph with $V$ vertices and let say I have an adjacency matrix of order $N$, how can I make sum of each column even?
Like I have a graph with $4$ vertices and $4$ edges as
$begin{bmatrix}0 & 1 & 0 &0 \
0 & 0 & 1 & 0\
0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 end{bmatrix}$
And I want to convert it like this,
$begin{bmatrix}0 & 0 & 0 &0 \
1 & 0 & 1 & 0\
0 & 0 & 0 & 0\
1 & 0 & 1 & 0 end{bmatrix}$
For reference, if $i^{th}$ element of the $j^{th}$ row is $1$ then the edge is directed from $j$ to $i$.
You can reverse any edge between two vertices such that the graph remains connected. And the adjacency matrix's indexing starts from 1 rather than from 0.
matrices discrete-mathematics graph-theory matrix-equations
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
$endgroup$
3
$begingroup$
Depends on what operations you allow yourself to use.
$endgroup$
– Michal Adamaszek
Dec 13 '18 at 6:54
$begingroup$
I've added the operation which you can use in the last sentence.
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:02
add a comment |
$begingroup$
Let $G$ be a connected graph with $V$ vertices and let say I have an adjacency matrix of order $N$, how can I make sum of each column even?
Like I have a graph with $4$ vertices and $4$ edges as
$begin{bmatrix}0 & 1 & 0 &0 \
0 & 0 & 1 & 0\
0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 end{bmatrix}$
And I want to convert it like this,
$begin{bmatrix}0 & 0 & 0 &0 \
1 & 0 & 1 & 0\
0 & 0 & 0 & 0\
1 & 0 & 1 & 0 end{bmatrix}$
For reference, if $i^{th}$ element of the $j^{th}$ row is $1$ then the edge is directed from $j$ to $i$.
You can reverse any edge between two vertices such that the graph remains connected. And the adjacency matrix's indexing starts from 1 rather than from 0.
matrices discrete-mathematics graph-theory matrix-equations
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
$endgroup$
Let $G$ be a connected graph with $V$ vertices and let say I have an adjacency matrix of order $N$, how can I make sum of each column even?
Like I have a graph with $4$ vertices and $4$ edges as
$begin{bmatrix}0 & 1 & 0 &0 \
0 & 0 & 1 & 0\
0 & 0 & 0 & 1 \
1 & 0 & 0 & 0 end{bmatrix}$
And I want to convert it like this,
$begin{bmatrix}0 & 0 & 0 &0 \
1 & 0 & 1 & 0\
0 & 0 & 0 & 0\
1 & 0 & 1 & 0 end{bmatrix}$
For reference, if $i^{th}$ element of the $j^{th}$ row is $1$ then the edge is directed from $j$ to $i$.
You can reverse any edge between two vertices such that the graph remains connected. And the adjacency matrix's indexing starts from 1 rather than from 0.
matrices discrete-mathematics graph-theory matrix-equations
matrices discrete-mathematics graph-theory matrix-equations
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
edited Dec 21 '18 at 7:01
Sahil Silare
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
asked Dec 13 '18 at 5:37
Sahil SilareSahil Silare
11619
11619
3
$begingroup$
Depends on what operations you allow yourself to use.
$endgroup$
– Michal Adamaszek
Dec 13 '18 at 6:54
$begingroup$
I've added the operation which you can use in the last sentence.
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:02
add a comment |
3
$begingroup$
Depends on what operations you allow yourself to use.
$endgroup$
– Michal Adamaszek
Dec 13 '18 at 6:54
$begingroup$
I've added the operation which you can use in the last sentence.
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:02
3
3
$begingroup$
Depends on what operations you allow yourself to use.
$endgroup$
– Michal Adamaszek
Dec 13 '18 at 6:54
$begingroup$
Depends on what operations you allow yourself to use.
$endgroup$
– Michal Adamaszek
Dec 13 '18 at 6:54
$begingroup$
I've added the operation which you can use in the last sentence.
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:02
$begingroup$
I've added the operation which you can use in the last sentence.
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:02
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As mentioned in the comments, this depends on what operations you allow, because you are clearly allowing your underlying graph to change --- the graph after your transformation isn't isomorphic to the first graph.
For your first matrix, you have the following graph:
For your second matrix, you have the following:
Taken as directed graphs, these are not isomorphic (however, if you relax them to merely undirected, they are). As such, it's difficult to determine what operations you're allowing as legal transformations.
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
$endgroup$
$begingroup$
I've added the allowed operation in the last sentence of the question. Can you elaborate your answer?
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:03
$begingroup$
@SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $begin{bmatrix} 1 & 0 \ 0 & 0 end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row.
$endgroup$
– apnorton
Dec 22 '18 at 17:42
$begingroup$
I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number.
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:48
$begingroup$
@SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$.
$endgroup$
– apnorton
Dec 22 '18 at 17:54
$begingroup$
Can't you just reverse the direction between 2 odd column indexes?
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:55
|
show 2 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3037641%2fmaking-column-sum-of-adjacency-matrix-even%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As mentioned in the comments, this depends on what operations you allow, because you are clearly allowing your underlying graph to change --- the graph after your transformation isn't isomorphic to the first graph.
For your first matrix, you have the following graph:
For your second matrix, you have the following:
Taken as directed graphs, these are not isomorphic (however, if you relax them to merely undirected, they are). As such, it's difficult to determine what operations you're allowing as legal transformations.
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
$endgroup$
$begingroup$
I've added the allowed operation in the last sentence of the question. Can you elaborate your answer?
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:03
$begingroup$
@SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $begin{bmatrix} 1 & 0 \ 0 & 0 end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row.
$endgroup$
– apnorton
Dec 22 '18 at 17:42
$begingroup$
I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number.
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:48
$begingroup$
@SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$.
$endgroup$
– apnorton
Dec 22 '18 at 17:54
$begingroup$
Can't you just reverse the direction between 2 odd column indexes?
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:55
|
show 2 more comments
$begingroup$
As mentioned in the comments, this depends on what operations you allow, because you are clearly allowing your underlying graph to change --- the graph after your transformation isn't isomorphic to the first graph.
For your first matrix, you have the following graph:
For your second matrix, you have the following:
Taken as directed graphs, these are not isomorphic (however, if you relax them to merely undirected, they are). As such, it's difficult to determine what operations you're allowing as legal transformations.
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
$endgroup$
$begingroup$
I've added the allowed operation in the last sentence of the question. Can you elaborate your answer?
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:03
$begingroup$
@SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $begin{bmatrix} 1 & 0 \ 0 & 0 end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row.
$endgroup$
– apnorton
Dec 22 '18 at 17:42
$begingroup$
I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number.
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:48
$begingroup$
@SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$.
$endgroup$
– apnorton
Dec 22 '18 at 17:54
$begingroup$
Can't you just reverse the direction between 2 odd column indexes?
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:55
|
show 2 more comments
$begingroup$
As mentioned in the comments, this depends on what operations you allow, because you are clearly allowing your underlying graph to change --- the graph after your transformation isn't isomorphic to the first graph.
For your first matrix, you have the following graph:
For your second matrix, you have the following:
Taken as directed graphs, these are not isomorphic (however, if you relax them to merely undirected, they are). As such, it's difficult to determine what operations you're allowing as legal transformations.
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
$endgroup$
As mentioned in the comments, this depends on what operations you allow, because you are clearly allowing your underlying graph to change --- the graph after your transformation isn't isomorphic to the first graph.
For your first matrix, you have the following graph:
For your second matrix, you have the following:
Taken as directed graphs, these are not isomorphic (however, if you relax them to merely undirected, they are). As such, it's difficult to determine what operations you're allowing as legal transformations.
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
answered Dec 14 '18 at 2:09
apnortonapnorton
15.2k33796
15.2k33796
$begingroup$
I've added the allowed operation in the last sentence of the question. Can you elaborate your answer?
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:03
$begingroup$
@SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $begin{bmatrix} 1 & 0 \ 0 & 0 end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row.
$endgroup$
– apnorton
Dec 22 '18 at 17:42
$begingroup$
I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number.
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:48
$begingroup$
@SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$.
$endgroup$
– apnorton
Dec 22 '18 at 17:54
$begingroup$
Can't you just reverse the direction between 2 odd column indexes?
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:55
|
show 2 more comments
$begingroup$
I've added the allowed operation in the last sentence of the question. Can you elaborate your answer?
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:03
$begingroup$
@SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $begin{bmatrix} 1 & 0 \ 0 & 0 end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row.
$endgroup$
– apnorton
Dec 22 '18 at 17:42
$begingroup$
I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number.
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:48
$begingroup$
@SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$.
$endgroup$
– apnorton
Dec 22 '18 at 17:54
$begingroup$
Can't you just reverse the direction between 2 odd column indexes?
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:55
$begingroup$
I've added the allowed operation in the last sentence of the question. Can you elaborate your answer?
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:03
$begingroup$
I've added the allowed operation in the last sentence of the question. Can you elaborate your answer?
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:03
$begingroup$
@SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $begin{bmatrix} 1 & 0 \ 0 & 0 end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row.
$endgroup$
– apnorton
Dec 22 '18 at 17:42
$begingroup$
@SahilSilare with those rules, you still might not be able to do so. Consider the graph formed by two nodes with one edge like so: $begin{bmatrix} 1 & 0 \ 0 & 0 end{bmatrix}$. No matter what, you can't get an even number of $1$'s in a single column/row.
$endgroup$
– apnorton
Dec 22 '18 at 17:42
$begingroup$
I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number.
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:48
$begingroup$
I'm not saying even number of ones, I'm saying to make the the sum of each column even, it can be either $0$ or $2$ or any even number.
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:48
$begingroup$
@SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$.
$endgroup$
– apnorton
Dec 22 '18 at 17:54
$begingroup$
@SahilSilare "even number of 1s" is equivalent to "even sum of values" since every value is $0$ or $1$.
$endgroup$
– apnorton
Dec 22 '18 at 17:54
$begingroup$
Can't you just reverse the direction between 2 odd column indexes?
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:55
$begingroup$
Can't you just reverse the direction between 2 odd column indexes?
$endgroup$
– Sahil Silare
Dec 22 '18 at 17:55
|
show 2 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3037641%2fmaking-column-sum-of-adjacency-matrix-even%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
Depends on what operations you allow yourself to use.
$endgroup$
– Michal Adamaszek
Dec 13 '18 at 6:54
$begingroup$
I've added the operation which you can use in the last sentence.
$endgroup$
– Sahil Silare
Dec 21 '18 at 7:02