M is nice if it is possible to make it all + by a set of operation, each consisting of changing the sign of one row or the sign of one column.Making a biased coin flip fairChessboard problem in IMO2014Count Shared CustomersExtremely difficult puzzle - related to algorithmsHow many distinct Unruly boards are there?Finding neighbours of a certain cell using modular arithmeticMy Simple Combinatorial Method to Enumerate All Sudoku Solution GridsFinding a combinatorial formula for the following sequence of tablesFilling a modified sudoku/latin squareGCD Euclid's algorithm as solution to the 2-buckets water puzzle

Strong empirical falsification of quantum mechanics based on vacuum energy density

It grows, but water kills it

Should I outline or discovery write my stories?

Is there a working SACD iso player for Ubuntu?

What if a revenant (monster) gains fire resistance?

What should you do when eye contact makes your subordinate uncomfortable?

How can Trident be so inexpensive? Will it orbit Triton or just do a (slow) flyby?

The IT department bottlenecks progress. How should I handle this?

Where does the bonus feat in the cleric starting package come from?

Should I stop contributing to retirement accounts?

Create all possible words using a set or letters

Longest common substring in linear time

How to explain what's wrong with this application of the chain rule?

Approximating irrational number to rational number

Why do compilers behave differently when static_cast(ing) a function to void*?

What does chmod -u do?

"Spoil" vs "Ruin"

Biological Blimps: Propulsion

Non-trope happy ending?

Store Credit Card Information in Password Manager?

Does an advisor owe his/her student anything? Will an advisor keep a PhD student only out of pity?

The screen of my macbook suddenly broken down how can I do to recover

250 Floor Tower

Why does the Sun have different day lengths, but not the gas giants?



M is nice if it is possible to make it all + by a set of operation, each consisting of changing the sign of one row or the sign of one column.


Making a biased coin flip fairChessboard problem in IMO2014Count Shared CustomersExtremely difficult puzzle - related to algorithmsHow many distinct Unruly boards are there?Finding neighbours of a certain cell using modular arithmeticMy Simple Combinatorial Method to Enumerate All Sudoku Solution GridsFinding a combinatorial formula for the following sequence of tablesFilling a modified sudoku/latin squareGCD Euclid's algorithm as solution to the 2-buckets water puzzle













0












$begingroup$


Let $M$ be an $ntimes n$ matrix whose entries are $+$ and $-$.
Call $M$ nice if it is possible
to make it all $+$ by a set of operation, each consisting of changing the sign of one
row or the sign of one column.



Design a simple and efficient algorithm for deciding
whether the given M is nice.



For starts, I think that the the number of $+$ must be a multiple of $n$ (i.e: $ 0, n, 2n,...,n*n $). But i am not sure how to prove/continue, I would be happy for some help.










share|cite|improve this question









$endgroup$











  • $begingroup$
    What about $$beginbmatrix&+&+&-\&-&-&+\&-&-&+endbmatrix$$ This is a nice $3times3$ matrix with $4$ plus sings. (Start by flipping the first row.)
    $endgroup$
    – saulspatz
    Mar 15 at 18:07











  • $begingroup$
    you are right :/ Thanks
    $endgroup$
    – yyyyt
    Mar 15 at 19:35











  • $begingroup$
    By the way: There is no need to restrict this niceness property to quadratic matrices.
    $endgroup$
    – Wolfgang Kais
    Mar 16 at 8:02















0












$begingroup$


Let $M$ be an $ntimes n$ matrix whose entries are $+$ and $-$.
Call $M$ nice if it is possible
to make it all $+$ by a set of operation, each consisting of changing the sign of one
row or the sign of one column.



Design a simple and efficient algorithm for deciding
whether the given M is nice.



For starts, I think that the the number of $+$ must be a multiple of $n$ (i.e: $ 0, n, 2n,...,n*n $). But i am not sure how to prove/continue, I would be happy for some help.










share|cite|improve this question









$endgroup$











  • $begingroup$
    What about $$beginbmatrix&+&+&-\&-&-&+\&-&-&+endbmatrix$$ This is a nice $3times3$ matrix with $4$ plus sings. (Start by flipping the first row.)
    $endgroup$
    – saulspatz
    Mar 15 at 18:07











  • $begingroup$
    you are right :/ Thanks
    $endgroup$
    – yyyyt
    Mar 15 at 19:35











  • $begingroup$
    By the way: There is no need to restrict this niceness property to quadratic matrices.
    $endgroup$
    – Wolfgang Kais
    Mar 16 at 8:02













0












0








0





$begingroup$


Let $M$ be an $ntimes n$ matrix whose entries are $+$ and $-$.
Call $M$ nice if it is possible
to make it all $+$ by a set of operation, each consisting of changing the sign of one
row or the sign of one column.



Design a simple and efficient algorithm for deciding
whether the given M is nice.



For starts, I think that the the number of $+$ must be a multiple of $n$ (i.e: $ 0, n, 2n,...,n*n $). But i am not sure how to prove/continue, I would be happy for some help.










share|cite|improve this question









$endgroup$




Let $M$ be an $ntimes n$ matrix whose entries are $+$ and $-$.
Call $M$ nice if it is possible
to make it all $+$ by a set of operation, each consisting of changing the sign of one
row or the sign of one column.



Design a simple and efficient algorithm for deciding
whether the given M is nice.



For starts, I think that the the number of $+$ must be a multiple of $n$ (i.e: $ 0, n, 2n,...,n*n $). But i am not sure how to prove/continue, I would be happy for some help.







puzzle






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Mar 15 at 17:57









yyyytyyyyt

31




31











  • $begingroup$
    What about $$beginbmatrix&+&+&-\&-&-&+\&-&-&+endbmatrix$$ This is a nice $3times3$ matrix with $4$ plus sings. (Start by flipping the first row.)
    $endgroup$
    – saulspatz
    Mar 15 at 18:07











  • $begingroup$
    you are right :/ Thanks
    $endgroup$
    – yyyyt
    Mar 15 at 19:35











  • $begingroup$
    By the way: There is no need to restrict this niceness property to quadratic matrices.
    $endgroup$
    – Wolfgang Kais
    Mar 16 at 8:02
















  • $begingroup$
    What about $$beginbmatrix&+&+&-\&-&-&+\&-&-&+endbmatrix$$ This is a nice $3times3$ matrix with $4$ plus sings. (Start by flipping the first row.)
    $endgroup$
    – saulspatz
    Mar 15 at 18:07











  • $begingroup$
    you are right :/ Thanks
    $endgroup$
    – yyyyt
    Mar 15 at 19:35











  • $begingroup$
    By the way: There is no need to restrict this niceness property to quadratic matrices.
    $endgroup$
    – Wolfgang Kais
    Mar 16 at 8:02















$begingroup$
What about $$beginbmatrix&+&+&-\&-&-&+\&-&-&+endbmatrix$$ This is a nice $3times3$ matrix with $4$ plus sings. (Start by flipping the first row.)
$endgroup$
– saulspatz
Mar 15 at 18:07





$begingroup$
What about $$beginbmatrix&+&+&-\&-&-&+\&-&-&+endbmatrix$$ This is a nice $3times3$ matrix with $4$ plus sings. (Start by flipping the first row.)
$endgroup$
– saulspatz
Mar 15 at 18:07













$begingroup$
you are right :/ Thanks
$endgroup$
– yyyyt
Mar 15 at 19:35





$begingroup$
you are right :/ Thanks
$endgroup$
– yyyyt
Mar 15 at 19:35













$begingroup$
By the way: There is no need to restrict this niceness property to quadratic matrices.
$endgroup$
– Wolfgang Kais
Mar 16 at 8:02




$begingroup$
By the way: There is no need to restrict this niceness property to quadratic matrices.
$endgroup$
– Wolfgang Kais
Mar 16 at 8:02










3 Answers
3






active

oldest

votes


















0












$begingroup$


A matrix is nice iff every row is equal or opposite to the first row.




Therefore, a simple algorithm is to check if each row is equal or opposite to the first row.



Proof: Suppose every row is either equal or opposite to the first row. Flip all rows which are opposite the first row, so now all rows are the same. Then, flip all negative columns.



Suppose $M$ is nice. Then there is a sequence of flips starting from the matrix $P$ whose entries are all $+$ and ending at $M$. Note $P$ has the property that every row is equal or opposite the first. Furthermore, flipping any row or column preserves this property. Therefore, $M$ has the property as well.






share|cite|improve this answer









$endgroup$












  • $begingroup$
    Very elegant !!
    $endgroup$
    – yyyyt
    Mar 19 at 13:56


















0












$begingroup$

Here are some hints to get you started.



A particular element changes sign if and only if the number of times its row is flipped, plus the number of times its column is odd. The order of the flips doesn't matter. Also, we see that there is no point in flipping a line more than once; flipping it twice is the same as not flipping it. So, we can assume each line is flipped at most once.



If two elements in the same column of a nice matrix have the same sign, then in changing to a matrix of all plus signs, their rows must be flipped the same number of number of times.






share|cite|improve this answer









$endgroup$




















    0












    $begingroup$

    Clearly, all (both) possible $1times 1$ matrices are nice. For $2times 2$ matices, we find that they are nice if and only if the number of entries that are $-$ is even. For larger matices, we see that if it is nice, then also every quadratic sub-matrix that can be obtained by removing rows and columns is (and must be) nice. If we want the check the niceness of a $ntimes n$ matrix this way, we see that for $n>2$, we must only check the $(n-1)^2$ $2times 2$ sub-matices in adjacent rows and columns. This might sound much, but the complexity is only $mathcalO(n^2)$, so it's barely different than checking all entries of the matrix.



    As @saulspatz already noted, there is no need to change a row or column more than once. To find a set of operations that turns a nice matrix into the "all $+$-matrix" (containing only $+$-entries), we can do the following: Find an initial $-$-entry and chose to "flip" its column as the initial element of our set of operations (we could also flip the row, which we will see later). Flipping this column, there might have been $+$-elements that are now $-$, so we must add the flippings of the corresponding rows to our set. After applying these operations, the initial column has turned to "all $+$". We won't change these entries again, because that would require an unneccessary operation to change it back. The row of the initial element (which we dont't flip) also might contain $-$-entries that need to be changed, so we must add the flippings of the corresponding columns to our set of operations. Now, after applying these operations, also the row of our initial element has become "all $+$". Any additional operation would affect either the row or the column of our initial element and thus would require an unneccessary operation to change it back, so our set of operations is complete and will turn the nice matrix into the "all $+$ matrix".



    The order in that we apply the operations doesn't matter, each operation is inverse to itself and flipping all rows and all columns will change every entry of the matrix twice, so applying all possible flippings, the matrix will be returned to its original state. There are only $2n$ possible operations, and if we have a set of $k$ operations, the complementary set of $2n-k$ operations will have the same resulting matrix. This means, that we will need at most $n$ operations to make a nice $ntimes n$ matrix the "all $+$-matrix" (and flipping the row of our initial element instead of ots column could be more efficient).



    At last: How many of the $2^n^2$ possible $ntimes n$ matices are nice? To count them, we can count the different resulting matrices when appling a possible set of flippings to the "all $+$-matrix". As we have seen, for each of the $2^2n$ possible sets of operations, the complementary set will have the same resulting matrix. Except for these duplicates, the results will all be different, so there are $2^2n-1$ nice $ntimes n$ matrices.



    Thanks for this nice question. :-)






    share|cite|improve this answer









    $endgroup$












      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
      );



      );













      draft saved

      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3149610%2fm-is-nice-if-it-is-possible-to-make-it-all-by-a-set-of-operation-each-consist%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      3 Answers
      3






      active

      oldest

      votes








      3 Answers
      3






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      0












      $begingroup$


      A matrix is nice iff every row is equal or opposite to the first row.




      Therefore, a simple algorithm is to check if each row is equal or opposite to the first row.



      Proof: Suppose every row is either equal or opposite to the first row. Flip all rows which are opposite the first row, so now all rows are the same. Then, flip all negative columns.



      Suppose $M$ is nice. Then there is a sequence of flips starting from the matrix $P$ whose entries are all $+$ and ending at $M$. Note $P$ has the property that every row is equal or opposite the first. Furthermore, flipping any row or column preserves this property. Therefore, $M$ has the property as well.






      share|cite|improve this answer









      $endgroup$












      • $begingroup$
        Very elegant !!
        $endgroup$
        – yyyyt
        Mar 19 at 13:56















      0












      $begingroup$


      A matrix is nice iff every row is equal or opposite to the first row.




      Therefore, a simple algorithm is to check if each row is equal or opposite to the first row.



      Proof: Suppose every row is either equal or opposite to the first row. Flip all rows which are opposite the first row, so now all rows are the same. Then, flip all negative columns.



      Suppose $M$ is nice. Then there is a sequence of flips starting from the matrix $P$ whose entries are all $+$ and ending at $M$. Note $P$ has the property that every row is equal or opposite the first. Furthermore, flipping any row or column preserves this property. Therefore, $M$ has the property as well.






      share|cite|improve this answer









      $endgroup$












      • $begingroup$
        Very elegant !!
        $endgroup$
        – yyyyt
        Mar 19 at 13:56













      0












      0








      0





      $begingroup$


      A matrix is nice iff every row is equal or opposite to the first row.




      Therefore, a simple algorithm is to check if each row is equal or opposite to the first row.



      Proof: Suppose every row is either equal or opposite to the first row. Flip all rows which are opposite the first row, so now all rows are the same. Then, flip all negative columns.



      Suppose $M$ is nice. Then there is a sequence of flips starting from the matrix $P$ whose entries are all $+$ and ending at $M$. Note $P$ has the property that every row is equal or opposite the first. Furthermore, flipping any row or column preserves this property. Therefore, $M$ has the property as well.






      share|cite|improve this answer









      $endgroup$




      A matrix is nice iff every row is equal or opposite to the first row.




      Therefore, a simple algorithm is to check if each row is equal or opposite to the first row.



      Proof: Suppose every row is either equal or opposite to the first row. Flip all rows which are opposite the first row, so now all rows are the same. Then, flip all negative columns.



      Suppose $M$ is nice. Then there is a sequence of flips starting from the matrix $P$ whose entries are all $+$ and ending at $M$. Note $P$ has the property that every row is equal or opposite the first. Furthermore, flipping any row or column preserves this property. Therefore, $M$ has the property as well.







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered Mar 16 at 22:56









      Mike EarnestMike Earnest

      25.6k22151




      25.6k22151











      • $begingroup$
        Very elegant !!
        $endgroup$
        – yyyyt
        Mar 19 at 13:56
















      • $begingroup$
        Very elegant !!
        $endgroup$
        – yyyyt
        Mar 19 at 13:56















      $begingroup$
      Very elegant !!
      $endgroup$
      – yyyyt
      Mar 19 at 13:56




      $begingroup$
      Very elegant !!
      $endgroup$
      – yyyyt
      Mar 19 at 13:56











      0












      $begingroup$

      Here are some hints to get you started.



      A particular element changes sign if and only if the number of times its row is flipped, plus the number of times its column is odd. The order of the flips doesn't matter. Also, we see that there is no point in flipping a line more than once; flipping it twice is the same as not flipping it. So, we can assume each line is flipped at most once.



      If two elements in the same column of a nice matrix have the same sign, then in changing to a matrix of all plus signs, their rows must be flipped the same number of number of times.






      share|cite|improve this answer









      $endgroup$

















        0












        $begingroup$

        Here are some hints to get you started.



        A particular element changes sign if and only if the number of times its row is flipped, plus the number of times its column is odd. The order of the flips doesn't matter. Also, we see that there is no point in flipping a line more than once; flipping it twice is the same as not flipping it. So, we can assume each line is flipped at most once.



        If two elements in the same column of a nice matrix have the same sign, then in changing to a matrix of all plus signs, their rows must be flipped the same number of number of times.






        share|cite|improve this answer









        $endgroup$















          0












          0








          0





          $begingroup$

          Here are some hints to get you started.



          A particular element changes sign if and only if the number of times its row is flipped, plus the number of times its column is odd. The order of the flips doesn't matter. Also, we see that there is no point in flipping a line more than once; flipping it twice is the same as not flipping it. So, we can assume each line is flipped at most once.



          If two elements in the same column of a nice matrix have the same sign, then in changing to a matrix of all plus signs, their rows must be flipped the same number of number of times.






          share|cite|improve this answer









          $endgroup$



          Here are some hints to get you started.



          A particular element changes sign if and only if the number of times its row is flipped, plus the number of times its column is odd. The order of the flips doesn't matter. Also, we see that there is no point in flipping a line more than once; flipping it twice is the same as not flipping it. So, we can assume each line is flipped at most once.



          If two elements in the same column of a nice matrix have the same sign, then in changing to a matrix of all plus signs, their rows must be flipped the same number of number of times.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Mar 15 at 18:30









          saulspatzsaulspatz

          17.1k31435




          17.1k31435





















              0












              $begingroup$

              Clearly, all (both) possible $1times 1$ matrices are nice. For $2times 2$ matices, we find that they are nice if and only if the number of entries that are $-$ is even. For larger matices, we see that if it is nice, then also every quadratic sub-matrix that can be obtained by removing rows and columns is (and must be) nice. If we want the check the niceness of a $ntimes n$ matrix this way, we see that for $n>2$, we must only check the $(n-1)^2$ $2times 2$ sub-matices in adjacent rows and columns. This might sound much, but the complexity is only $mathcalO(n^2)$, so it's barely different than checking all entries of the matrix.



              As @saulspatz already noted, there is no need to change a row or column more than once. To find a set of operations that turns a nice matrix into the "all $+$-matrix" (containing only $+$-entries), we can do the following: Find an initial $-$-entry and chose to "flip" its column as the initial element of our set of operations (we could also flip the row, which we will see later). Flipping this column, there might have been $+$-elements that are now $-$, so we must add the flippings of the corresponding rows to our set. After applying these operations, the initial column has turned to "all $+$". We won't change these entries again, because that would require an unneccessary operation to change it back. The row of the initial element (which we dont't flip) also might contain $-$-entries that need to be changed, so we must add the flippings of the corresponding columns to our set of operations. Now, after applying these operations, also the row of our initial element has become "all $+$". Any additional operation would affect either the row or the column of our initial element and thus would require an unneccessary operation to change it back, so our set of operations is complete and will turn the nice matrix into the "all $+$ matrix".



              The order in that we apply the operations doesn't matter, each operation is inverse to itself and flipping all rows and all columns will change every entry of the matrix twice, so applying all possible flippings, the matrix will be returned to its original state. There are only $2n$ possible operations, and if we have a set of $k$ operations, the complementary set of $2n-k$ operations will have the same resulting matrix. This means, that we will need at most $n$ operations to make a nice $ntimes n$ matrix the "all $+$-matrix" (and flipping the row of our initial element instead of ots column could be more efficient).



              At last: How many of the $2^n^2$ possible $ntimes n$ matices are nice? To count them, we can count the different resulting matrices when appling a possible set of flippings to the "all $+$-matrix". As we have seen, for each of the $2^2n$ possible sets of operations, the complementary set will have the same resulting matrix. Except for these duplicates, the results will all be different, so there are $2^2n-1$ nice $ntimes n$ matrices.



              Thanks for this nice question. :-)






              share|cite|improve this answer









              $endgroup$

















                0












                $begingroup$

                Clearly, all (both) possible $1times 1$ matrices are nice. For $2times 2$ matices, we find that they are nice if and only if the number of entries that are $-$ is even. For larger matices, we see that if it is nice, then also every quadratic sub-matrix that can be obtained by removing rows and columns is (and must be) nice. If we want the check the niceness of a $ntimes n$ matrix this way, we see that for $n>2$, we must only check the $(n-1)^2$ $2times 2$ sub-matices in adjacent rows and columns. This might sound much, but the complexity is only $mathcalO(n^2)$, so it's barely different than checking all entries of the matrix.



                As @saulspatz already noted, there is no need to change a row or column more than once. To find a set of operations that turns a nice matrix into the "all $+$-matrix" (containing only $+$-entries), we can do the following: Find an initial $-$-entry and chose to "flip" its column as the initial element of our set of operations (we could also flip the row, which we will see later). Flipping this column, there might have been $+$-elements that are now $-$, so we must add the flippings of the corresponding rows to our set. After applying these operations, the initial column has turned to "all $+$". We won't change these entries again, because that would require an unneccessary operation to change it back. The row of the initial element (which we dont't flip) also might contain $-$-entries that need to be changed, so we must add the flippings of the corresponding columns to our set of operations. Now, after applying these operations, also the row of our initial element has become "all $+$". Any additional operation would affect either the row or the column of our initial element and thus would require an unneccessary operation to change it back, so our set of operations is complete and will turn the nice matrix into the "all $+$ matrix".



                The order in that we apply the operations doesn't matter, each operation is inverse to itself and flipping all rows and all columns will change every entry of the matrix twice, so applying all possible flippings, the matrix will be returned to its original state. There are only $2n$ possible operations, and if we have a set of $k$ operations, the complementary set of $2n-k$ operations will have the same resulting matrix. This means, that we will need at most $n$ operations to make a nice $ntimes n$ matrix the "all $+$-matrix" (and flipping the row of our initial element instead of ots column could be more efficient).



                At last: How many of the $2^n^2$ possible $ntimes n$ matices are nice? To count them, we can count the different resulting matrices when appling a possible set of flippings to the "all $+$-matrix". As we have seen, for each of the $2^2n$ possible sets of operations, the complementary set will have the same resulting matrix. Except for these duplicates, the results will all be different, so there are $2^2n-1$ nice $ntimes n$ matrices.



                Thanks for this nice question. :-)






                share|cite|improve this answer









                $endgroup$















                  0












                  0








                  0





                  $begingroup$

                  Clearly, all (both) possible $1times 1$ matrices are nice. For $2times 2$ matices, we find that they are nice if and only if the number of entries that are $-$ is even. For larger matices, we see that if it is nice, then also every quadratic sub-matrix that can be obtained by removing rows and columns is (and must be) nice. If we want the check the niceness of a $ntimes n$ matrix this way, we see that for $n>2$, we must only check the $(n-1)^2$ $2times 2$ sub-matices in adjacent rows and columns. This might sound much, but the complexity is only $mathcalO(n^2)$, so it's barely different than checking all entries of the matrix.



                  As @saulspatz already noted, there is no need to change a row or column more than once. To find a set of operations that turns a nice matrix into the "all $+$-matrix" (containing only $+$-entries), we can do the following: Find an initial $-$-entry and chose to "flip" its column as the initial element of our set of operations (we could also flip the row, which we will see later). Flipping this column, there might have been $+$-elements that are now $-$, so we must add the flippings of the corresponding rows to our set. After applying these operations, the initial column has turned to "all $+$". We won't change these entries again, because that would require an unneccessary operation to change it back. The row of the initial element (which we dont't flip) also might contain $-$-entries that need to be changed, so we must add the flippings of the corresponding columns to our set of operations. Now, after applying these operations, also the row of our initial element has become "all $+$". Any additional operation would affect either the row or the column of our initial element and thus would require an unneccessary operation to change it back, so our set of operations is complete and will turn the nice matrix into the "all $+$ matrix".



                  The order in that we apply the operations doesn't matter, each operation is inverse to itself and flipping all rows and all columns will change every entry of the matrix twice, so applying all possible flippings, the matrix will be returned to its original state. There are only $2n$ possible operations, and if we have a set of $k$ operations, the complementary set of $2n-k$ operations will have the same resulting matrix. This means, that we will need at most $n$ operations to make a nice $ntimes n$ matrix the "all $+$-matrix" (and flipping the row of our initial element instead of ots column could be more efficient).



                  At last: How many of the $2^n^2$ possible $ntimes n$ matices are nice? To count them, we can count the different resulting matrices when appling a possible set of flippings to the "all $+$-matrix". As we have seen, for each of the $2^2n$ possible sets of operations, the complementary set will have the same resulting matrix. Except for these duplicates, the results will all be different, so there are $2^2n-1$ nice $ntimes n$ matrices.



                  Thanks for this nice question. :-)






                  share|cite|improve this answer









                  $endgroup$



                  Clearly, all (both) possible $1times 1$ matrices are nice. For $2times 2$ matices, we find that they are nice if and only if the number of entries that are $-$ is even. For larger matices, we see that if it is nice, then also every quadratic sub-matrix that can be obtained by removing rows and columns is (and must be) nice. If we want the check the niceness of a $ntimes n$ matrix this way, we see that for $n>2$, we must only check the $(n-1)^2$ $2times 2$ sub-matices in adjacent rows and columns. This might sound much, but the complexity is only $mathcalO(n^2)$, so it's barely different than checking all entries of the matrix.



                  As @saulspatz already noted, there is no need to change a row or column more than once. To find a set of operations that turns a nice matrix into the "all $+$-matrix" (containing only $+$-entries), we can do the following: Find an initial $-$-entry and chose to "flip" its column as the initial element of our set of operations (we could also flip the row, which we will see later). Flipping this column, there might have been $+$-elements that are now $-$, so we must add the flippings of the corresponding rows to our set. After applying these operations, the initial column has turned to "all $+$". We won't change these entries again, because that would require an unneccessary operation to change it back. The row of the initial element (which we dont't flip) also might contain $-$-entries that need to be changed, so we must add the flippings of the corresponding columns to our set of operations. Now, after applying these operations, also the row of our initial element has become "all $+$". Any additional operation would affect either the row or the column of our initial element and thus would require an unneccessary operation to change it back, so our set of operations is complete and will turn the nice matrix into the "all $+$ matrix".



                  The order in that we apply the operations doesn't matter, each operation is inverse to itself and flipping all rows and all columns will change every entry of the matrix twice, so applying all possible flippings, the matrix will be returned to its original state. There are only $2n$ possible operations, and if we have a set of $k$ operations, the complementary set of $2n-k$ operations will have the same resulting matrix. This means, that we will need at most $n$ operations to make a nice $ntimes n$ matrix the "all $+$-matrix" (and flipping the row of our initial element instead of ots column could be more efficient).



                  At last: How many of the $2^n^2$ possible $ntimes n$ matices are nice? To count them, we can count the different resulting matrices when appling a possible set of flippings to the "all $+$-matrix". As we have seen, for each of the $2^2n$ possible sets of operations, the complementary set will have the same resulting matrix. Except for these duplicates, the results will all be different, so there are $2^2n-1$ nice $ntimes n$ matrices.



                  Thanks for this nice question. :-)







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Mar 16 at 7:54









                  Wolfgang KaisWolfgang Kais

                  8165




                  8165



























                      draft saved

                      draft discarded
















































                      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.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3149610%2fm-is-nice-if-it-is-possible-to-make-it-all-by-a-set-of-operation-each-consist%23new-answer', 'question_page');

                      );

                      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







                      Popular posts from this blog

                      How should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer

                      random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

                      Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye