Usbrth

Was credit for the black hole image misattributed?

Can a non-EU citizen traveling with me come with me through the EU passport line?

Mortgage adviser recommends a longer term than necessary combined with overpayments

How to rotate it perfectly?

Can smartphones with the same camera sensor have different image quality?

What to do with post with dry rot?

How can you insert a "times/divide" symbol similar to the "plus/minus" (±) one?

How many things? AとBがふたつ

What LEGO pieces have "real-world" functionality?

Area of a 2D convex hull

When communicating altitude with a '9' in it, should it be pronounced "nine hundred" or "niner hundred"?

Slither Like a Snake

Why use gamma over alpha radiation?

What can I do if my MacBook isn’t charging but already ran out?

How can I make names more distinctive without making them longer?

Can I throw a longsword at someone?

What's the point in a preamp?

What items from the Roman-age tech-level could be used to deter all creatures from entering a small area?

Fishing simulator

Are my PIs rude or am I just being too sensitive?

Biased dice probability question

Active filter with series inductor and resistor - do these exist?

Estimate capacitor parameters

Training a classifier when some of the features are unknown

Algorithm to obtain the null matrix from a series of predefined operators

1

$begingroup$

Consider a matrix $tilde A$ of size $(N+2)times (N+2)$ whose coefficients are either $0$ or $1$.

Denote $A$ the submatrix containing columns from 2 to $N$ of $tilde A$
and line from $2$ to $N$ of $tilde A$.
In short $A=tilde A(2...N,2...N)$.

Define the following elementary operator:
$$b_i^j(A) = A + E_i,j+ E_i,j+1+ E_i+1,j+ E_i-1,j+ E_i,j-1 quad textmod; [2]$$
for all $i,j$ of $mathbf1,ldots, N$ where $E_a,b$ is the elementary matrix (which has 0 everywhere except for the coefficient in position $(a,b)$).

Is it possible to transform any submatrix $Min M_N,N(0,1)$ of a matrix $tilde Min M_N+2,N+2(0,1)$ to the null matrix of $M_N,N(0,1)$ using these operations $b_i^j$ ?

Remark: Assuming the existence of such algorithm and applying it to the matrix $tilde M$, we obtain a matrix denoted as $tilde M_infty$. We do not care about the coefficients of the first and last columns/lines of $tilde M_infty$, we only care that the submatrix $M_infty=tilde M_infty(2...N,2...N)$ is null.

linear-algebra abstract-algebra matrices algorithms modular-arithmetic

share|cite|improve this question

edited Apr 9 at 0:13

Smilia

asked Apr 8 at 20:20

SmiliaSmilia

733617

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you really want to reduce anything modulo $2 pi$ ? That's a fairly foreign object in the algebraic setting in which the rest of your problem is happening. (Most likely, it changes nothing, since $pi$ is rational and so the fractional part of your entries will give away how often you have added $2 pi$...)
  $endgroup$
  – darij grinberg
  Apr 8 at 21:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  On the other hand, if your "$mod 2pi$" is meant to be a "$mod 2$", then you are studying "button madness" (aka "lights-out") on a square board, and this has seen some research (at least on a torus: win.tue.nl/~aeb/ca/madness/mad.html ).
  $endgroup$
  – darij grinberg
  Apr 8 at 21:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  indeed, it's mod 2 .... yeah I would like to solve the button madness? I didn't expect it was so complicated
  $endgroup$
  – Smilia
  Apr 9 at 0:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The link doesn't study the same problem that you are studying (as the link works with a toroidal grid), so maybe yours is actually simpler.
  $endgroup$
  – darij grinberg
  Apr 9 at 1:52
  

  
  
  
  

add a comment | 

1

$begingroup$

Consider a matrix $tilde A$ of size $(N+2)times (N+2)$ whose coefficients are either $0$ or $1$.

Denote $A$ the submatrix containing columns from 2 to $N$ of $tilde A$
and line from $2$ to $N$ of $tilde A$.
In short $A=tilde A(2...N,2...N)$.

Define the following elementary operator:
$$b_i^j(A) = A + E_i,j+ E_i,j+1+ E_i+1,j+ E_i-1,j+ E_i,j-1 quad textmod; [2]$$
for all $i,j$ of $mathbf1,ldots, N$ where $E_a,b$ is the elementary matrix (which has 0 everywhere except for the coefficient in position $(a,b)$).

Is it possible to transform any submatrix $Min M_N,N(0,1)$ of a matrix $tilde Min M_N+2,N+2(0,1)$ to the null matrix of $M_N,N(0,1)$ using these operations $b_i^j$ ?

Remark: Assuming the existence of such algorithm and applying it to the matrix $tilde M$, we obtain a matrix denoted as $tilde M_infty$. We do not care about the coefficients of the first and last columns/lines of $tilde M_infty$, we only care that the submatrix $M_infty=tilde M_infty(2...N,2...N)$ is null.

linear-algebra abstract-algebra matrices algorithms modular-arithmetic

share|cite|improve this question

edited Apr 9 at 0:13

Smilia

asked Apr 8 at 20:20

SmiliaSmilia

733617

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you really want to reduce anything modulo $2 pi$ ? That's a fairly foreign object in the algebraic setting in which the rest of your problem is happening. (Most likely, it changes nothing, since $pi$ is rational and so the fractional part of your entries will give away how often you have added $2 pi$...)
  $endgroup$
  – darij grinberg
  Apr 8 at 21:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  On the other hand, if your "$mod 2pi$" is meant to be a "$mod 2$", then you are studying "button madness" (aka "lights-out") on a square board, and this has seen some research (at least on a torus: win.tue.nl/~aeb/ca/madness/mad.html ).
  $endgroup$
  – darij grinberg
  Apr 8 at 21:33
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  indeed, it's mod 2 .... yeah I would like to solve the button madness? I didn't expect it was so complicated
  $endgroup$
  – Smilia
  Apr 9 at 0:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The link doesn't study the same problem that you are studying (as the link works with a toroidal grid), so maybe yours is actually simpler.
  $endgroup$
  – darij grinberg
  Apr 9 at 1:52
  

  
  
  
  

add a comment | 

$begingroup$

Consider a matrix $tilde A$ of size $(N+2)times (N+2)$ whose coefficients are either $0$ or $1$.

Denote $A$ the submatrix containing columns from 2 to $N$ of $tilde A$
and line from $2$ to $N$ of $tilde A$.
In short $A=tilde A(2...N,2...N)$.

Define the following elementary operator:
$$b_i^j(A) = A + E_i,j+ E_i,j+1+ E_i+1,j+ E_i-1,j+ E_i,j-1 quad textmod; [2]$$
for all $i,j$ of $mathbf1,ldots, N$ where $E_a,b$ is the elementary matrix (which has 0 everywhere except for the coefficient in position $(a,b)$).

Is it possible to transform any submatrix $Min M_N,N(0,1)$ of a matrix $tilde Min M_N+2,N+2(0,1)$ to the null matrix of $M_N,N(0,1)$ using these operations $b_i^j$ ?

Remark: Assuming the existence of such algorithm and applying it to the matrix $tilde M$, we obtain a matrix denoted as $tilde M_infty$. We do not care about the coefficients of the first and last columns/lines of $tilde M_infty$, we only care that the submatrix $M_infty=tilde M_infty(2...N,2...N)$ is null.

linear-algebra abstract-algebra matrices algorithms modular-arithmetic

share|cite|improve this question

edited Apr 9 at 0:13

Smilia

asked Apr 8 at 20:20

SmiliaSmilia

733617

$endgroup$

share|cite|improve this question

edited Apr 9 at 0:13

Smilia

asked Apr 8 at 20:20

SmiliaSmilia

733617

share|cite|improve this question

edited Apr 9 at 0:13

Smilia

asked Apr 8 at 20:20

SmiliaSmilia

733617

asked Apr 8 at 20:20

SmiliaSmilia

733617

asked Apr 8 at 20:20

SmiliaSmilia

733617