# A matrix solution ?

• Oct 1st 2009, 08:19 PM
tanvi.azgaonkar
A matrix solution ?
hello all,

I have this advanced computer and math problem that I have to solve.

it goes something like this
Matrix A is given of order n where n <=100
Matrix B is given of the same order n<=100 as A
Elements of A and B are 1's and 0's
We have to achieve B from A. For achieving B from A we can do the following 2 operations
1 - complement any row of matrix A
2 - complement any column of matrix A

The solution is minimum number of complements row-wise along with the index of the complemented rows and minimum number of complements column-wise along with index of complemented columns.
If no solution is possible then simply write the answer as -1
The matrix index starts from 0.

Example :

n = 3

A =
0 0 0
1 1 0
1 1 0

B =
1 1 0
1 1 1
1 1 1

now to get B from A.
Ans :
Number of row complements = 1
Row index that have to be complemented = 0
Number of column complements = 1
Column index that have to be complements = 2

Simulation of solution

Row : 0 index complement
A =
0--> 1 1 1
1--- 1 1 0
2--- 1 1 0

Column : 2 index complement
A =
1 1 0
1 1 1
1 1 1

Thus in these 2 operations we get A == B

So can a mathematical solution exist here ?
Theres a similar game called lights off which has a math solution , so i thought this is very similar to that game and probably might have a math solution which I am unable to figure out !!

Thanks for reading patiently

Tanvi
• Oct 11th 2009, 04:32 AM
tanvi.azgaonkar
Have I posted the query in the wrong place ?

To the mods : The addition is because I was wondering there was no reply from anyone in 10 days that it has to be either a real tough nut or I have posted to query in the wrong section.