What is the total number of distinct $mtimes n$ matrices in row canonical form using only $0$s and $1$s? The Next CEO of Stack OverflowHelp regarding row echelon and reduced row echelon formIssue understanding the difference between reduced row echelon form on a coefficient matrix and on an augmented matrixSuppose that A and B are nxn matrices with A row equivalent to B. Prove that if A is nonsingular, then B is row equivalent to In.Is the zero matrix in reduced row echelon form?Row equivalent matrices and provingWhy can the row-reduced echelon matrix $R$ only be identity matrix?Row equivalent matrices and row spacesAre these matrices in row echelon form?Computing all binary matrices with given row and column sumWhat is the computational cost of reduced row echelon form (RREF) of a rectangular matrix A?
Which one is the true statement?
How to avoid supervisors with prejudiced views?
How to get the last not-null value in an ordered column of a huge table?
Yu-Gi-Oh cards in Python 3
Can you teleport closer to a creature you are Frightened of?
Computationally populating tables with probability data
Is it correct to say moon starry nights?
Spaces in which all closed sets are regular closed
Help/tips for a first time writer?
Pulling the principal components out of a DimensionReducerFunction?
Lucky Feat: How can "more than one creature spend a luck point to influence the outcome of a roll"?
Where do students learn to solve polynomial equations these days?
What would be the main consequences for a country leaving the WTO?
From jafe to El-Guest
Expectation in a stochastic differential equation
Purpose of level-shifter with same in and out voltages
Strange use of "whether ... than ..." in official text
Help understanding this unsettling image of Titan, Epimetheus, and Saturn's rings?
How do I fit a non linear curve?
Is it ok to trim down a tube patch?
What connection does MS Office have to Netscape Navigator?
My ex-girlfriend uses my Apple ID to login to her iPad, do I have to give her my Apple ID password to reset it?
Help! I cannot understand this game’s notations!
How did Beeri the Hittite come up with naming his daughter Yehudit?
What is the total number of distinct $mtimes n$ matrices in row canonical form using only $0$s and $1$s?
The Next CEO of Stack OverflowHelp regarding row echelon and reduced row echelon formIssue understanding the difference between reduced row echelon form on a coefficient matrix and on an augmented matrixSuppose that A and B are nxn matrices with A row equivalent to B. Prove that if A is nonsingular, then B is row equivalent to In.Is the zero matrix in reduced row echelon form?Row equivalent matrices and provingWhy can the row-reduced echelon matrix $R$ only be identity matrix?Row equivalent matrices and row spacesAre these matrices in row echelon form?Computing all binary matrices with given row and column sumWhat is the computational cost of reduced row echelon form (RREF) of a rectangular matrix A?
$begingroup$
Suppose that $A$ is an $m times n$ matrix over a field $F$. What is the total number $N$ of the distinct matrices in row-reduced echelon form that are row equivalent to $A$ and that only have entires either $0$s or $1$s?
I know that this number $N$ is $5$ if $A$ is $2 times 2$, and that $N$ is 16 if $A$ is $3times 3$. Am I right?
Can a general formula be obtained?
We can assume without any loss of generality that $F$ is the field $mathbbR$ of real numbers. Am I right?
linear-algebra combinatorics matrices
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
$endgroup$
add a comment |
$begingroup$
Suppose that $A$ is an $m times n$ matrix over a field $F$. What is the total number $N$ of the distinct matrices in row-reduced echelon form that are row equivalent to $A$ and that only have entires either $0$s or $1$s?
I know that this number $N$ is $5$ if $A$ is $2 times 2$, and that $N$ is 16 if $A$ is $3times 3$. Am I right?
Can a general formula be obtained?
We can assume without any loss of generality that $F$ is the field $mathbbR$ of real numbers. Am I right?
linear-algebra combinatorics matrices
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
$endgroup$
$begingroup$
I really don't think you meant "that are row equivalent to $A$". For example, there is no matrix with entries in $0,1$ that is row equivalent to $pmatrix1 & pi cr 0 & 0cr$.
$endgroup$
– Robert Israel
Mar 19 at 20:38
add a comment |
$begingroup$
Suppose that $A$ is an $m times n$ matrix over a field $F$. What is the total number $N$ of the distinct matrices in row-reduced echelon form that are row equivalent to $A$ and that only have entires either $0$s or $1$s?
I know that this number $N$ is $5$ if $A$ is $2 times 2$, and that $N$ is 16 if $A$ is $3times 3$. Am I right?
Can a general formula be obtained?
We can assume without any loss of generality that $F$ is the field $mathbbR$ of real numbers. Am I right?
linear-algebra combinatorics matrices
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
$endgroup$
Suppose that $A$ is an $m times n$ matrix over a field $F$. What is the total number $N$ of the distinct matrices in row-reduced echelon form that are row equivalent to $A$ and that only have entires either $0$s or $1$s?
I know that this number $N$ is $5$ if $A$ is $2 times 2$, and that $N$ is 16 if $A$ is $3times 3$. Am I right?
Can a general formula be obtained?
We can assume without any loss of generality that $F$ is the field $mathbbR$ of real numbers. Am I right?
linear-algebra combinatorics matrices
linear-algebra combinatorics matrices
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
asked Mar 19 at 20:03
Saaqib MahmoodSaaqib Mahmood
7,92542581
7,92542581
$begingroup$
I really don't think you meant "that are row equivalent to $A$". For example, there is no matrix with entries in $0,1$ that is row equivalent to $pmatrix1 & pi cr 0 & 0cr$.
$endgroup$
– Robert Israel
Mar 19 at 20:38
add a comment |
$begingroup$
I really don't think you meant "that are row equivalent to $A$". For example, there is no matrix with entries in $0,1$ that is row equivalent to $pmatrix1 & pi cr 0 & 0cr$.
$endgroup$
– Robert Israel
Mar 19 at 20:38
$begingroup$
I really don't think you meant "that are row equivalent to $A$". For example, there is no matrix with entries in $0,1$ that is row equivalent to $pmatrix1 & pi cr 0 & 0cr$.
$endgroup$
– Robert Israel
Mar 19 at 20:38
$begingroup$
I really don't think you meant "that are row equivalent to $A$". For example, there is no matrix with entries in $0,1$ that is row equivalent to $pmatrix1 & pi cr 0 & 0cr$.
$endgroup$
– Robert Israel
Mar 19 at 20:38
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
An $m times n$ matrix of rank $k$ in RREF will have $k$ leading ones, which can be in any $k$ of the $n$ columns. There are $n choose k$ ways to choose these if $0 le k le min(m,n)$. Suppose those are columns $j_1 < j_2 < ldots < j_k$. In row $i$ (for $i le k$) we have $n - j_i - (k-i)$ "free" positions where there can be either $0$ or $1$.
Thus for a given choice of $j_1, ldots, j_k$ there are a total of $M = nk + frack-k^22 - sum_i=1^k j_i$ free positions, and this corresponds to $2^M$ of those matrices.
Hmm: it looks to me like in the case $mge n$ this is OEIS sequence A006116.
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
$endgroup$
add a comment |
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%2f3154534%2fwhat-is-the-total-number-of-distinct-m-times-n-matrices-in-row-canonical-form%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$
An $m times n$ matrix of rank $k$ in RREF will have $k$ leading ones, which can be in any $k$ of the $n$ columns. There are $n choose k$ ways to choose these if $0 le k le min(m,n)$. Suppose those are columns $j_1 < j_2 < ldots < j_k$. In row $i$ (for $i le k$) we have $n - j_i - (k-i)$ "free" positions where there can be either $0$ or $1$.
Thus for a given choice of $j_1, ldots, j_k$ there are a total of $M = nk + frack-k^22 - sum_i=1^k j_i$ free positions, and this corresponds to $2^M$ of those matrices.
Hmm: it looks to me like in the case $mge n$ this is OEIS sequence A006116.
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
$endgroup$
add a comment |
$begingroup$
An $m times n$ matrix of rank $k$ in RREF will have $k$ leading ones, which can be in any $k$ of the $n$ columns. There are $n choose k$ ways to choose these if $0 le k le min(m,n)$. Suppose those are columns $j_1 < j_2 < ldots < j_k$. In row $i$ (for $i le k$) we have $n - j_i - (k-i)$ "free" positions where there can be either $0$ or $1$.
Thus for a given choice of $j_1, ldots, j_k$ there are a total of $M = nk + frack-k^22 - sum_i=1^k j_i$ free positions, and this corresponds to $2^M$ of those matrices.
Hmm: it looks to me like in the case $mge n$ this is OEIS sequence A006116.
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
$endgroup$
add a comment |
$begingroup$
An $m times n$ matrix of rank $k$ in RREF will have $k$ leading ones, which can be in any $k$ of the $n$ columns. There are $n choose k$ ways to choose these if $0 le k le min(m,n)$. Suppose those are columns $j_1 < j_2 < ldots < j_k$. In row $i$ (for $i le k$) we have $n - j_i - (k-i)$ "free" positions where there can be either $0$ or $1$.
Thus for a given choice of $j_1, ldots, j_k$ there are a total of $M = nk + frack-k^22 - sum_i=1^k j_i$ free positions, and this corresponds to $2^M$ of those matrices.
Hmm: it looks to me like in the case $mge n$ this is OEIS sequence A006116.
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
$endgroup$
An $m times n$ matrix of rank $k$ in RREF will have $k$ leading ones, which can be in any $k$ of the $n$ columns. There are $n choose k$ ways to choose these if $0 le k le min(m,n)$. Suppose those are columns $j_1 < j_2 < ldots < j_k$. In row $i$ (for $i le k$) we have $n - j_i - (k-i)$ "free" positions where there can be either $0$ or $1$.
Thus for a given choice of $j_1, ldots, j_k$ there are a total of $M = nk + frack-k^22 - sum_i=1^k j_i$ free positions, and this corresponds to $2^M$ of those matrices.
Hmm: it looks to me like in the case $mge n$ this is OEIS sequence A006116.
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
answered Mar 19 at 21:26
Robert IsraelRobert Israel
330k23218473
330k23218473
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%2f3154534%2fwhat-is-the-total-number-of-distinct-m-times-n-matrices-in-row-canonical-form%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
$begingroup$
I really don't think you meant "that are row equivalent to $A$". For example, there is no matrix with entries in $0,1$ that is row equivalent to $pmatrix1 & pi cr 0 & 0cr$.
$endgroup$
– Robert Israel
Mar 19 at 20:38