The fantastic matrix
$begingroup$
Here's another question that I have been asked in an interview lately.
Let $M$ be an $n × n$ matrix whose values are $”+”$ and $”-”$. M is called fantastic if it is possible to make all it's values $”+”$ by a set of operations, when each only consisting of changing the sign of one
column or the sign of one row.
I was asked to: Design a simple,efficient algorithm to decide whether a matrix $M$ is fantastic.
calculation-puzzle computer-puzzle algorithm
asked Mar 30 at 8:56
JayJay
2006
$endgroup$
add a comment |
$begingroup$
Here's another question that I have been asked in an interview lately.
Let $M$ be an $n × n$ matrix whose values are $”+”$ and $”-”$. M is called fantastic if it is possible to make all it's values $”+”$ by a set of operations, when each only consisting of changing the sign of one
column or the sign of one row.
I was asked to: Design a simple,efficient algorithm to decide whether a matrix $M$ is fantastic.
calculation-puzzle computer-puzzle algorithm
asked Mar 30 at 8:56
JayJay
2006
$endgroup$
add a comment |
$begingroup$
Here's another question that I have been asked in an interview lately.
Let $M$ be an $n × n$ matrix whose values are $”+”$ and $”-”$. M is called fantastic if it is possible to make all it's values $”+”$ by a set of operations, when each only consisting of changing the sign of one
column or the sign of one row.
I was asked to: Design a simple,efficient algorithm to decide whether a matrix $M$ is fantastic.
calculation-puzzle computer-puzzle algorithm
asked Mar 30 at 8:56
JayJay
2006
$endgroup$
Here's another question that I have been asked in an interview lately.
Let $M$ be an $n × n$ matrix whose values are $”+”$ and $”-”$. M is called fantastic if it is possible to make all it's values $”+”$ by a set of operations, when each only consisting of changing the sign of one
column or the sign of one row.
I was asked to: Design a simple,efficient algorithm to decide whether a matrix $M$ is fantastic.
calculation-puzzle computer-puzzle algorithm
calculation-puzzle computer-puzzle algorithm
asked Mar 30 at 8:56
JayJay
2006
asked Mar 30 at 8:56
JayJay
2006
edited Mar 30 at 13:47
Jay
asked Mar 30 at 8:56
JayJay
2006
asked Mar 30 at 8:56
JayJay
2006
asked Mar 30 at 8:56
JayJay
2006
2006
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I think the following simple algorithm would work
A matrix is fantastic if and only if each row is either the same as the first row or the negative of the first row.
Equivalently
If we change "+" and "-" to $1$ and $-1$ then a matrix is fantastic if and only if it has rank $1$.
Proof
Consider the viewpoint where we have each "+" represented by $1$ and each "-" represented by $-1$. Each operation is now equivalent to multiplying a single row or a single column by $-1$. Each fantastic matrix can be obtained by applying a sequence of such operations to the matrix consisting entirely of $1$s.
Now, such an operation does not alter the rank of a matrix (if the changed row/column was a linear combination of the others then it still is) so any fantastic matrix necessarily has rank $1$. This proves the only if statement.
To prove the "if" statement, consider any matrix of rank $1$ with entries $pm 1$. Identify all entries which are $-1$ in the top row, say they have indices $i_1, i_2, ldots, i_m$.
Change all the entries in columns $i_1, i_2, ldots, i_m$.
Then, the rows in the resulting matrix will either have all $1$s or all $-1$s. Select the rows which are all $-1$s and change these to get back to a matrix of all $1$s.
answered Mar 30 at 9:42
hexominohexomino
47k4142221
$endgroup$
$begingroup$
Yea, I was thinking on the lines of determinants, but this is essentially equivalent.
$endgroup$
– Don Thousand
Mar 30 at 14:44
add a comment |
$begingroup$
Each row and column can either be switched or un-switched. Assume $ngt2$ (because otherwise the answer is trivial), and at least two rows/columns have been switched. Note that not all the R/C's have been switched, because again the answer is trivial. This results in a pattern such that if $(a,b)$ and $(c,d)$ are positive, then so are $(a,d)$ and $(c,b)$. so check that this is the case for all positive cells, and the matrix is fantastic! Note this also tells you which R/C's to switch to restore the pluses.
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fpuzzling.stackexchange.com%2fquestions%2f81199%2fthe-fantastic-matrix%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$
I think the following simple algorithm would work
A matrix is fantastic if and only if each row is either the same as the first row or the negative of the first row.
Equivalently
If we change "+" and "-" to $1$ and $-1$ then a matrix is fantastic if and only if it has rank $1$.
Proof
Consider the viewpoint where we have each "+" represented by $1$ and each "-" represented by $-1$. Each operation is now equivalent to multiplying a single row or a single column by $-1$. Each fantastic matrix can be obtained by applying a sequence of such operations to the matrix consisting entirely of $1$s.
Now, such an operation does not alter the rank of a matrix (if the changed row/column was a linear combination of the others then it still is) so any fantastic matrix necessarily has rank $1$. This proves the only if statement.
To prove the "if" statement, consider any matrix of rank $1$ with entries $pm 1$. Identify all entries which are $-1$ in the top row, say they have indices $i_1, i_2, ldots, i_m$.
Change all the entries in columns $i_1, i_2, ldots, i_m$.
Then, the rows in the resulting matrix will either have all $1$s or all $-1$s. Select the rows which are all $-1$s and change these to get back to a matrix of all $1$s.
answered Mar 30 at 9:42
hexominohexomino
47k4142221
$endgroup$
$begingroup$
Yea, I was thinking on the lines of determinants, but this is essentially equivalent.
$endgroup$
– Don Thousand
Mar 30 at 14:44
add a comment |
$begingroup$
I think the following simple algorithm would work
A matrix is fantastic if and only if each row is either the same as the first row or the negative of the first row.
Equivalently
If we change "+" and "-" to $1$ and $-1$ then a matrix is fantastic if and only if it has rank $1$.
Proof
Consider the viewpoint where we have each "+" represented by $1$ and each "-" represented by $-1$. Each operation is now equivalent to multiplying a single row or a single column by $-1$. Each fantastic matrix can be obtained by applying a sequence of such operations to the matrix consisting entirely of $1$s.
Now, such an operation does not alter the rank of a matrix (if the changed row/column was a linear combination of the others then it still is) so any fantastic matrix necessarily has rank $1$. This proves the only if statement.
To prove the "if" statement, consider any matrix of rank $1$ with entries $pm 1$. Identify all entries which are $-1$ in the top row, say they have indices $i_1, i_2, ldots, i_m$.
Change all the entries in columns $i_1, i_2, ldots, i_m$.
Then, the rows in the resulting matrix will either have all $1$s or all $-1$s. Select the rows which are all $-1$s and change these to get back to a matrix of all $1$s.
answered Mar 30 at 9:42
hexominohexomino
47k4142221
$endgroup$
$begingroup$
Yea, I was thinking on the lines of determinants, but this is essentially equivalent.
$endgroup$
– Don Thousand
Mar 30 at 14:44
add a comment |
$begingroup$
I think the following simple algorithm would work
A matrix is fantastic if and only if each row is either the same as the first row or the negative of the first row.
Equivalently
If we change "+" and "-" to $1$ and $-1$ then a matrix is fantastic if and only if it has rank $1$.
Proof
Consider the viewpoint where we have each "+" represented by $1$ and each "-" represented by $-1$. Each operation is now equivalent to multiplying a single row or a single column by $-1$. Each fantastic matrix can be obtained by applying a sequence of such operations to the matrix consisting entirely of $1$s.
Now, such an operation does not alter the rank of a matrix (if the changed row/column was a linear combination of the others then it still is) so any fantastic matrix necessarily has rank $1$. This proves the only if statement.
To prove the "if" statement, consider any matrix of rank $1$ with entries $pm 1$. Identify all entries which are $-1$ in the top row, say they have indices $i_1, i_2, ldots, i_m$.
Change all the entries in columns $i_1, i_2, ldots, i_m$.
Then, the rows in the resulting matrix will either have all $1$s or all $-1$s. Select the rows which are all $-1$s and change these to get back to a matrix of all $1$s.
answered Mar 30 at 9:42
hexominohexomino
47k4142221
$endgroup$
I think the following simple algorithm would work
A matrix is fantastic if and only if each row is either the same as the first row or the negative of the first row.
Equivalently
If we change "+" and "-" to $1$ and $-1$ then a matrix is fantastic if and only if it has rank $1$.
Proof
Consider the viewpoint where we have each "+" represented by $1$ and each "-" represented by $-1$. Each operation is now equivalent to multiplying a single row or a single column by $-1$. Each fantastic matrix can be obtained by applying a sequence of such operations to the matrix consisting entirely of $1$s.
Now, such an operation does not alter the rank of a matrix (if the changed row/column was a linear combination of the others then it still is) so any fantastic matrix necessarily has rank $1$. This proves the only if statement.
To prove the "if" statement, consider any matrix of rank $1$ with entries $pm 1$. Identify all entries which are $-1$ in the top row, say they have indices $i_1, i_2, ldots, i_m$.
Change all the entries in columns $i_1, i_2, ldots, i_m$.
Then, the rows in the resulting matrix will either have all $1$s or all $-1$s. Select the rows which are all $-1$s and change these to get back to a matrix of all $1$s.
answered Mar 30 at 9:42
hexominohexomino
47k4142221
edited Mar 30 at 11:30
answered Mar 30 at 9:42
hexominohexomino
47k4142221
answered Mar 30 at 9:42
hexominohexomino
47k4142221
answered Mar 30 at 9:42
hexominohexomino
47k4142221
47k4142221
$begingroup$
Yea, I was thinking on the lines of determinants, but this is essentially equivalent.
$endgroup$
– Don Thousand
Mar 30 at 14:44
add a comment |
$begingroup$
Yea, I was thinking on the lines of determinants, but this is essentially equivalent.
$endgroup$
– Don Thousand
Mar 30 at 14:44
$begingroup$
Yea, I was thinking on the lines of determinants, but this is essentially equivalent.
$endgroup$
– Don Thousand
Mar 30 at 14:44
$begingroup$
Yea, I was thinking on the lines of determinants, but this is essentially equivalent.
$endgroup$
– Don Thousand
Mar 30 at 14:44
add a comment |
$begingroup$
Each row and column can either be switched or un-switched. Assume $ngt2$ (because otherwise the answer is trivial), and at least two rows/columns have been switched. Note that not all the R/C's have been switched, because again the answer is trivial. This results in a pattern such that if $(a,b)$ and $(c,d)$ are positive, then so are $(a,d)$ and $(c,b)$. so check that this is the case for all positive cells, and the matrix is fantastic! Note this also tells you which R/C's to switch to restore the pluses.
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
$endgroup$
add a comment |
$begingroup$
Each row and column can either be switched or un-switched. Assume $ngt2$ (because otherwise the answer is trivial), and at least two rows/columns have been switched. Note that not all the R/C's have been switched, because again the answer is trivial. This results in a pattern such that if $(a,b)$ and $(c,d)$ are positive, then so are $(a,d)$ and $(c,b)$. so check that this is the case for all positive cells, and the matrix is fantastic! Note this also tells you which R/C's to switch to restore the pluses.
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
$endgroup$
add a comment |
$begingroup$
Each row and column can either be switched or un-switched. Assume $ngt2$ (because otherwise the answer is trivial), and at least two rows/columns have been switched. Note that not all the R/C's have been switched, because again the answer is trivial. This results in a pattern such that if $(a,b)$ and $(c,d)$ are positive, then so are $(a,d)$ and $(c,b)$. so check that this is the case for all positive cells, and the matrix is fantastic! Note this also tells you which R/C's to switch to restore the pluses.
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
$endgroup$
Each row and column can either be switched or un-switched. Assume $ngt2$ (because otherwise the answer is trivial), and at least two rows/columns have been switched. Note that not all the R/C's have been switched, because again the answer is trivial. This results in a pattern such that if $(a,b)$ and $(c,d)$ are positive, then so are $(a,d)$ and $(c,b)$. so check that this is the case for all positive cells, and the matrix is fantastic! Note this also tells you which R/C's to switch to restore the pluses.
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
edited Mar 30 at 12:19
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
answered Mar 30 at 9:38
JonMark PerryJonMark Perry
20.7k64099
20.7k64099
add a comment |
add a comment |
Thanks for contributing an answer to Puzzling 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%2fpuzzling.stackexchange.com%2fquestions%2f81199%2fthe-fantastic-matrix%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
