Equivalence classes of binary matrices under permutations of rows/columnsHow many permutations with this set...
Difference between 'demás' and 'otros'?
How do I spend money in Sweden and Denmark?
Does anycast addressing add additional latency in any way?
Cross over of arrows in a complex diagram
Why does the numerical solution of an ODE move away from an unstable equilibrium?
What shortcut does ⌦ symbol in Camunda macOS app indicate and how to invoke it?
Should I include salary information on my CV?
Does a centaur PC also count as being mounted?
Is it bad to describe a character long after their introduction?
Which centaur is more 'official'?
What is the line crossing the Pacific Ocean that is shown on maps?
How hard is it to sell a home which is currently mortgaged?
Can I travel from Germany to England alone as an unaccompanied minor?
Generate and graph the Recamán Sequence
Did Chinese school textbook maps (c. 1951) "depict China as stretching even into the central Asian republics"?
Procedurally generate regions on island
For people who believe in Jesus and not the devil, what happend in the desert?
Was touching your nose a greeting in second millenium Mesopotamia?
Why does this function call behave sensibly after calling it through a typecasted function pointer?
How can I check type T is among parameter pack Ts... in C++?
What is the olden name for sideburns?
Bash echo $-1 prints hb1. Why?
MH370 blackbox - is it still possible to retrieve data from it?
ArcGIS Intersect Tool not splitting lines as expected?
Equivalence classes of binary matrices under permutations of rows/columns
How many permutations with this set of rows and columns?Is the determinant of a matrix preserved under permutations of the rows/columns of a matrix?Equivalence classes of similar $2times 2$ matricesA canonical form for this equivalence relation on matricesNumber of matrices with no repeated columns or rowsPermutation of rows and columns of matricesCharacterization of $(0 ,1)$-matrices under swap of columns or rowsNumber of equivalence classes of matrices under switching rows and columnsStudying equivalence relation on matrices defined by permutation of rows and columnsNumber of permutations of matrices with unique rows and columns
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$begingroup$
Consider an MxN matrix A consisting entirely of 1's and 0's.
Let C be the equivalence class of A under permutations of its rows and permutations of its columns (but not rows with columns).
Given A, how can I compute an invariant of C which is different for different equivalence classes?
How many classes are there for a given M and N?
linear-algebra combinatorics matrices
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
$endgroup$
add a comment |
$begingroup$
Consider an MxN matrix A consisting entirely of 1's and 0's.
Let C be the equivalence class of A under permutations of its rows and permutations of its columns (but not rows with columns).
Given A, how can I compute an invariant of C which is different for different equivalence classes?
How many classes are there for a given M and N?
linear-algebra combinatorics matrices
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
$endgroup$
add a comment |
$begingroup$
Consider an MxN matrix A consisting entirely of 1's and 0's.
Let C be the equivalence class of A under permutations of its rows and permutations of its columns (but not rows with columns).
Given A, how can I compute an invariant of C which is different for different equivalence classes?
How many classes are there for a given M and N?
linear-algebra combinatorics matrices
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
$endgroup$
Consider an MxN matrix A consisting entirely of 1's and 0's.
Let C be the equivalence class of A under permutations of its rows and permutations of its columns (but not rows with columns).
Given A, how can I compute an invariant of C which is different for different equivalence classes?
How many classes are there for a given M and N?
linear-algebra combinatorics matrices
linear-algebra combinatorics matrices
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
asked 10 hours ago
EINSTEIN WAS WRONGEINSTEIN WAS WRONG
186 bronze badges
186 bronze badges
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
It is not at all easy to count how many classes there are for a given $M$ and $N$. Mostly because to even know the size of particular equivalence class, you need to know the size of its stabilizer group.
Each such binary matrix corresponds to a bipartite graph with $M$ vertices in the first part and $N$ vertices in the second part. Equivalence classes under permutations of rows/columns correspond to isomorphism classes of graphs, where the two parts are distinguished (and so are not allowed to be swapped). Computing the size of the stabilizer group of a matrix is thus equivalent to computing the automorphism group of the associated graph. This is a hard problem. Counting the number of nonisomorphic bipartite graphs is also very hard (though I think it can be done using Polya enumeration).
Your best bet for an invariant for the equivalence classes is to come up with a canonical form; if you can impose an order on the set of matrices, then you can represent an equivalence class with the "smallest" of its members. (You can look up "canonical graph labeling" to get an idea of how this works.)
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
$endgroup$
add a comment |
$begingroup$
Partial answer.
You can assume $m le n$.
There are clearly $n+1$ classes when $m=1$: all that matters is the number of $1$s in the only row.
In general, the two multisets that specify the number of $1$s in the rows and in the columns are clearly invariant. They are a complete set of invariants for the $2 times 2$ case.
In the general case, any pair of multisets with the right cardinalities and equal sums will represent some set of equivalence classes. Swapping all the $1$'s for $0$s and vice versa halves the difficulty of the analysis.
Counting classes is at least as hard as the corresponding partition counting problem.
Are the multisets a complete set of invariants, or do you need to refine them? I suggest you work out the $2 times 3$ and perhaps $3times 3$ cases by brute force to see what might be going on.
@MorganRodgers 's answer suggests that this is a hard problem.
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
$endgroup$
add a comment |
Your Answer
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%2f3272018%2fequivalence-classes-of-binary-matrices-under-permutations-of-rows-columns%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It is not at all easy to count how many classes there are for a given $M$ and $N$. Mostly because to even know the size of particular equivalence class, you need to know the size of its stabilizer group.
Each such binary matrix corresponds to a bipartite graph with $M$ vertices in the first part and $N$ vertices in the second part. Equivalence classes under permutations of rows/columns correspond to isomorphism classes of graphs, where the two parts are distinguished (and so are not allowed to be swapped). Computing the size of the stabilizer group of a matrix is thus equivalent to computing the automorphism group of the associated graph. This is a hard problem. Counting the number of nonisomorphic bipartite graphs is also very hard (though I think it can be done using Polya enumeration).
Your best bet for an invariant for the equivalence classes is to come up with a canonical form; if you can impose an order on the set of matrices, then you can represent an equivalence class with the "smallest" of its members. (You can look up "canonical graph labeling" to get an idea of how this works.)
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
$endgroup$
add a comment |
$begingroup$
It is not at all easy to count how many classes there are for a given $M$ and $N$. Mostly because to even know the size of particular equivalence class, you need to know the size of its stabilizer group.
Each such binary matrix corresponds to a bipartite graph with $M$ vertices in the first part and $N$ vertices in the second part. Equivalence classes under permutations of rows/columns correspond to isomorphism classes of graphs, where the two parts are distinguished (and so are not allowed to be swapped). Computing the size of the stabilizer group of a matrix is thus equivalent to computing the automorphism group of the associated graph. This is a hard problem. Counting the number of nonisomorphic bipartite graphs is also very hard (though I think it can be done using Polya enumeration).
Your best bet for an invariant for the equivalence classes is to come up with a canonical form; if you can impose an order on the set of matrices, then you can represent an equivalence class with the "smallest" of its members. (You can look up "canonical graph labeling" to get an idea of how this works.)
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
$endgroup$
add a comment |
$begingroup$
It is not at all easy to count how many classes there are for a given $M$ and $N$. Mostly because to even know the size of particular equivalence class, you need to know the size of its stabilizer group.
Each such binary matrix corresponds to a bipartite graph with $M$ vertices in the first part and $N$ vertices in the second part. Equivalence classes under permutations of rows/columns correspond to isomorphism classes of graphs, where the two parts are distinguished (and so are not allowed to be swapped). Computing the size of the stabilizer group of a matrix is thus equivalent to computing the automorphism group of the associated graph. This is a hard problem. Counting the number of nonisomorphic bipartite graphs is also very hard (though I think it can be done using Polya enumeration).
Your best bet for an invariant for the equivalence classes is to come up with a canonical form; if you can impose an order on the set of matrices, then you can represent an equivalence class with the "smallest" of its members. (You can look up "canonical graph labeling" to get an idea of how this works.)
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
$endgroup$
It is not at all easy to count how many classes there are for a given $M$ and $N$. Mostly because to even know the size of particular equivalence class, you need to know the size of its stabilizer group.
Each such binary matrix corresponds to a bipartite graph with $M$ vertices in the first part and $N$ vertices in the second part. Equivalence classes under permutations of rows/columns correspond to isomorphism classes of graphs, where the two parts are distinguished (and so are not allowed to be swapped). Computing the size of the stabilizer group of a matrix is thus equivalent to computing the automorphism group of the associated graph. This is a hard problem. Counting the number of nonisomorphic bipartite graphs is also very hard (though I think it can be done using Polya enumeration).
Your best bet for an invariant for the equivalence classes is to come up with a canonical form; if you can impose an order on the set of matrices, then you can represent an equivalence class with the "smallest" of its members. (You can look up "canonical graph labeling" to get an idea of how this works.)
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
answered 9 hours ago
Morgan RodgersMorgan Rodgers
10.5k3 gold badges16 silver badges41 bronze badges
10.5k3 gold badges16 silver badges41 bronze badges
add a comment |
add a comment |
$begingroup$
Partial answer.
You can assume $m le n$.
There are clearly $n+1$ classes when $m=1$: all that matters is the number of $1$s in the only row.
In general, the two multisets that specify the number of $1$s in the rows and in the columns are clearly invariant. They are a complete set of invariants for the $2 times 2$ case.
In the general case, any pair of multisets with the right cardinalities and equal sums will represent some set of equivalence classes. Swapping all the $1$'s for $0$s and vice versa halves the difficulty of the analysis.
Counting classes is at least as hard as the corresponding partition counting problem.
Are the multisets a complete set of invariants, or do you need to refine them? I suggest you work out the $2 times 3$ and perhaps $3times 3$ cases by brute force to see what might be going on.
@MorganRodgers 's answer suggests that this is a hard problem.
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
$endgroup$
add a comment |
$begingroup$
Partial answer.
You can assume $m le n$.
There are clearly $n+1$ classes when $m=1$: all that matters is the number of $1$s in the only row.
In general, the two multisets that specify the number of $1$s in the rows and in the columns are clearly invariant. They are a complete set of invariants for the $2 times 2$ case.
In the general case, any pair of multisets with the right cardinalities and equal sums will represent some set of equivalence classes. Swapping all the $1$'s for $0$s and vice versa halves the difficulty of the analysis.
Counting classes is at least as hard as the corresponding partition counting problem.
Are the multisets a complete set of invariants, or do you need to refine them? I suggest you work out the $2 times 3$ and perhaps $3times 3$ cases by brute force to see what might be going on.
@MorganRodgers 's answer suggests that this is a hard problem.
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
$endgroup$
add a comment |
$begingroup$
Partial answer.
You can assume $m le n$.
There are clearly $n+1$ classes when $m=1$: all that matters is the number of $1$s in the only row.
In general, the two multisets that specify the number of $1$s in the rows and in the columns are clearly invariant. They are a complete set of invariants for the $2 times 2$ case.
In the general case, any pair of multisets with the right cardinalities and equal sums will represent some set of equivalence classes. Swapping all the $1$'s for $0$s and vice versa halves the difficulty of the analysis.
Counting classes is at least as hard as the corresponding partition counting problem.
Are the multisets a complete set of invariants, or do you need to refine them? I suggest you work out the $2 times 3$ and perhaps $3times 3$ cases by brute force to see what might be going on.
@MorganRodgers 's answer suggests that this is a hard problem.
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
$endgroup$
Partial answer.
You can assume $m le n$.
There are clearly $n+1$ classes when $m=1$: all that matters is the number of $1$s in the only row.
In general, the two multisets that specify the number of $1$s in the rows and in the columns are clearly invariant. They are a complete set of invariants for the $2 times 2$ case.
In the general case, any pair of multisets with the right cardinalities and equal sums will represent some set of equivalence classes. Swapping all the $1$'s for $0$s and vice versa halves the difficulty of the analysis.
Counting classes is at least as hard as the corresponding partition counting problem.
Are the multisets a complete set of invariants, or do you need to refine them? I suggest you work out the $2 times 3$ and perhaps $3times 3$ cases by brute force to see what might be going on.
@MorganRodgers 's answer suggests that this is a hard problem.
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
edited 9 hours ago
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
answered 9 hours ago
Ethan BolkerEthan Bolker
51.2k5 gold badges60 silver badges130 bronze badges
51.2k5 gold badges60 silver badges130 bronze badges
add a comment |
add a comment |
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%2f3272018%2fequivalence-classes-of-binary-matrices-under-permutations-of-rows-columns%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
