|
Science Forum Index » Math - Symbolic Forum » Bring an arbitrary nxn Boolean matrix to a goal matrix (deve
Page 1 of 1
|
| Author |
Message |
| John Lee |
 Posted: Sun Nov 05, 2006 11:43 pm |
|
|
|
Guest
|
Hello, I have a distracting problem (which may pull you in too!)
A – Arbitrary square Boolean matrix
T – Target matrix
Goals:
The second goal is to bring A to T in the fewest number of XOR operations.
The first goal is to determine which A’s are indeed ‘solvable’.
Restrictions:
1) All matrices are square
2) All elements are Boolean
3) Columns can be XOR’d together
4) Rows can be XOR’d together
5) No row or column exchanges are allowed
An example sequence of operations:
(Please view with a fixed-width font like Courier New)
A T
| 1 0 1 | | 1 1 1 | | 1 1 1 |
| 0 0 0 | --> | 0 0 0 | --> | 1 1 1 |
| 1 0 1 | | 1 1 1 | | 1 1 1 |
C1 ^ C2 R1 ^ R2
2x2 cases:
If T = |1 1| then the following (9) are ‘solvable’:
|1 1|
|10| |01| |00| |00| |11| |10| |01| |00| |11|
|00| |00| |10| |01| |00| |10| |01| |11| |11|
But these (7) are not ‘solvable’ to T:
|00| |10| |01| |01| |11| |10| |11|
|00| |01| |10| |11| |10| |11| |01|
I came up with one test-of-fitness method, but I can’t generalize it for
different T’s.
Here is the method I used for T = |1 1|:
|1 1|
1) Zero any duplicate columns or rows.
2) XOR all the columns together.
3) Check if this new column vector already exists in the matrix after step
(1). If not, then it can’t be ‘solved’.
4) XOR all the rows together.
5) Check if this new row vector already exists in the matrix after step (1).
If so, then the original matrix can be solved.
This method works for any sized square matrix. For example, there are only
49 3x3 matrices that can be ‘solved’.
How can I determine which square matrices can be solved for any target T?
Any ideas?
e.g. T = |0 1 0| for all 3x3's
|1 0 1|
|0 1 0|
Thanks,
Eric |
|
|
| Back to top |
|
| Toby Kelsey |
| Posted: Mon Nov 06, 2006 9:22 am |
|
|
|
Guest
|
John Lee wrote:
Quote: 5) No row or column exchanges are allowed
The following sequence exchanges columns/rows A and B
A <= AxB, B <= AxB, A <= AxB
So they are.
Toby |
|
|
| Back to top |
|
| Eric D. |
| Posted: Mon Nov 06, 2006 11:00 am |
|
|
|
Guest
|
| > 5) No row or column exchanges are allowed
|
| The following sequence exchanges columns/rows A and B
| A <= AxB, B <= AxB, A <= AxB
Thanks Toby,
These are clearly XOR operations, not row exchanges, so they are indeed
legal. It's just that the requirement is for people out there to not swap
rows/columns like in the rref algorithm. What you have written out should
be a natural consequence of an algorithm which 'solves' the matrix.
Do you have any suggestions about my first requirement?
Thanks,
Eric |
|
|
| Back to top |
|
| Toby Kelsey |
| Posted: Mon Nov 06, 2006 1:06 pm |
|
|
|
Guest
|
Operations are reversible, so you are talking about equivalence classes of
matrices. For 2x2 matrices you have 2 equivalence classes:
Quote: |10| |01| |00| |00| |11| |10| |01| |00| |11|
|00| |00| |10| |01| |00| |10| |01| |11| |11|
and
Quote: |00| |10| |01| |01| |11| |10| |11|
|00| |01| |10| |11| |10| |11| |01|
Let's say the canonical forms are
|00|
|01|
and
|00|
|00|
respectively.
Quote: How can I determine which square matrices can be solved for any target T?
Starting at the top left corner and working down and right, transform each 2x2
submatrix to its canonical form. You will end up with one of the 2x2 canonical
forms in the bottom rightmost part, all other entries being zero. If T and your
matrix are in the same equivalence class, it is solvable.
This works for any rectangular matrix.
Toby |
|
|
| Back to top |
|
| Jimserac |
| Posted: Sun Nov 12, 2006 8:32 pm |
|
|
|
Guest
|
John Lee wrote:
Quote: Hello, I have a distracting problem (which may pull you in too!)
A - Arbitrary square Boolean matrix
T - Target matrix
Goals:
The second goal is to bring A to T in the fewest number of XOR operations.
The first goal is to determine which A's are indeed 'solvable'.
This problem was extensively analyzed in the early 90's by
French crystallographer and physicist Gerard Langlet
(died 1995). He appears to have invented
his own paradigms of computation which made
analogies between Sierpinski fractals and a data
structure which he called a "Geniton" which was
a booean matrix.
Regretfully his writings are scattered.
However his program to solve the above mentioned problem
(or one very similar to it) is available as an APL workspace
(Langlet worked in APL).
You'll have to Google to locate the links, but I believe
its at the Univ of Waterloo APL repository.
You wlll, of course, have to search for an old
dos APL interpreter to run it - this may prove
more difficult than the problem itself.
Jimserac |
|
|
| Back to top |
|
| jasen |
| Posted: Sun Dec 31, 2006 11:08 pm |
|
|
|
Guest
|
On 2006-11-06, John Lee <datasniper@hotmail.com> wrote:
Quote: Restrictions:
1) All matrices are square
2) All elements are Boolean
3) Columns can be XOR’d together
4) Rows can be XOR’d together
5) No row or column exchanges are allowed
pointless restriction. exchanges can be done using 3 xors.
a ^= b
b ^= a
a ^= b
solvable: any where T is full of 0 or A has atleast one 1.
Quote: But these (7) are not ‘solvable’ to T:
|00| |10| |01| |01| |11| |10| |11|
|00| |01| |10| |11| |10| |11| |01|
they are if you allow xoring a row or column with itself.
--
Bye.
Jasen |
|
|
| Back to top |
|
| jasen |
| Posted: Sun Dec 31, 2006 11:10 pm |
|
|
|
Guest
|
On 2006-11-06, Eric D. <datasniper@hotmail.com> wrote:
Quote: | > 5) No row or column exchanges are allowed
|
| The following sequence exchanges columns/rows A and B
| A <= AxB, B <= AxB, A <= AxB
Thanks Toby,
These are clearly XOR operations, not row exchanges, so they are indeed
legal. It's just that the requirement is for people out there to not swap
rows/columns like in the rref algorithm. What you have written out should
be a natural consequence of an algorithm which 'solves' the matrix.
Do you have any suggestions about my first requirement?
all non square, non-null matrices are solvable
--
Bye.
Jasen |
|
|
| Back to top |
|
| |
