JIGYASA

An online placement forum.


You are not connected. Please login or register

Matrix a[N][N]

Go down  Message [Page 1 of 1]

1 Matrix a[N][N] on Wed Apr 07, 2010 5:11 am

Lucifer


Admin
Given an N*N array.... each element of the array is represented by a[i][j] where i and j vary from 1 to N...
Now, each row of the array contains nos. from 1 to N in some order.. Also, it is given that a[i][j] = a[j][i] for i = 1, 2,...,N and j=1,2,3,...,N... Prove that if N is odd then the nos. a[1][1], a[2][2], ... a[N][N] are 1,2,3...N in some order....

View user profile http://jigyasa.forumn.org

2 clarification on Fri Apr 09, 2010 3:20 am

I think that you should add that the numbers in a row and in a column are distinct!

Hint: Think of Sudoku

View user profile

3 @indranil.. on Fri Apr 09, 2010 3:26 am

Lucifer


Admin
By saying "Now, each row of the array contains nos. from 1 to N in some order".. i meant that each row contains all nos. from 1 to N exactly once in some order...

View user profile http://jigyasa.forumn.org

4 Re: Matrix a[N][N] on Fri Apr 09, 2010 3:30 am

Lucifer wrote:By saying "Now, each row of the array contains nos. from 1 to N in some order".. i meant that each row contains all nos. from 1 to N exactly once in some order...

Got it sirjee!!! Rolling Eyes bounce

View user profile

5 Re: Matrix a[N][N] on Tue Sep 21, 2010 7:24 am

Lucifer


Admin
As mentioned, each row contains elements from 1 to N. In that case, if N is odd then the no. of 1's, 2's, 3's,.... N's in the N*N array is odd.
( no. of 1's = no. of 2's = ....= no. of i's =....= no. of N's = N ( which is odd))
- (1)

We know that the diagonal divides the array into 2 equal halves. Also, given that a[i][j] = a[j][i].
Hence, it can be said that the no. of times an element is present in one half of the array = no. of times the same element is present in the other half.
- (2)

Therefore, for any element present in the 2 halves of the array ( except the diagonal ), the no. of occurrences of the same element is even (from (2)).
- (3)

But, from (1) it can be seen that the total no. of occurrences of any element in the array shall be odd.
Hence, from (1) and (3) it can be deduced that all the nos. a[1][1], a[2][2], ... a[N][N] are 1,2,3...N (in some order) to make the total no. of occurrences odd ( if N is odd ).

View user profile http://jigyasa.forumn.org

Sponsored content


Back to top  Message [Page 1 of 1]

Permissions in this forum:
You cannot reply to topics in this forum