46 votes

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$, non-zero elements, (i.e elements of lower triangle) of each row are stored one after another, starting from the first row, the index of the $(i, j)^{th}$ element of the lower triangular matrix in this new representation is:

- $i+j$
- $i+j-1$
- $(j-1)+\frac{i(i-1)}{2}$
- $i+\frac{j(j-1)}{2}$

17

in a lower triangular matrix, i th row contains (i +1) number of non zero elements.

Let's count how many elements are there before arr[i,j]----> If we assume array index starts from 0 then,

before i th row there are i rows(row 0 to i-1) , and in total these rows has 1+2+3.....+i =i(i+1)/2 elements(row 0 has 1 element, row 1 has 2 elements, .... row i-1 has i elements)

Now at i row, before j th element there are j elements(starting from arr[i,0] to arr[i,j-1]),

Hence in total before arr[i,j] there are (i(i+1)/2 + j) elements and those elements will have indexes

0 to (i(i+1)/2 + j -1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have index i(i+1)/2 + j in this new single dimensional compact array.

But none of the option is i(i+1)/2 + j, Actually, they have considered array indexes starting from 1 .

If we assume Array index starting from 1 then,

i th row contains i number of non zero elements.

before i th row there are i -1 rows(row 1 to i-1) , and in total these rows has 1+2+3.....+(i-1)= i((i-1)/2 elements(row 1 has 1 element, row 2 has 2 elements, .... row i-1 has i-1 elements)

Now at i th row, before j th element there are (j-1) elements(starting from arr[i,1] to arr[i,j-1]),

Hence in total before arr[i,j] there are (i(i-1)/2 + j-1) elements and those elements will have indexes

1 to (i(i-1)/2 + j-1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have index i(i-1)/2 + j in this new single dimensional compact array. Answer C.

Let's count how many elements are there before arr[i,j]----> If we assume array index starts from 0 then,

before i th row there are i rows(row 0 to i-1) , and in total these rows has 1+2+3.....+i =i(i+1)/2 elements(row 0 has 1 element, row 1 has 2 elements, .... row i-1 has i elements)

Now at i row, before j th element there are j elements(starting from arr[i,0] to arr[i,j-1]),

Hence in total before arr[i,j] there are (i(i+1)/2 + j) elements and those elements will have indexes

0 to (i(i+1)/2 + j -1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have index i(i+1)/2 + j in this new single dimensional compact array.

But none of the option is i(i+1)/2 + j, Actually, they have considered array indexes starting from 1 .

If we assume Array index starting from 1 then,

i th row contains i number of non zero elements.

before i th row there are i -1 rows(row 1 to i-1) , and in total these rows has 1+2+3.....+(i-1)= i((i-1)/2 elements(row 1 has 1 element, row 2 has 2 elements, .... row i-1 has i-1 elements)

Now at i th row, before j th element there are (j-1) elements(starting from arr[i,1] to arr[i,j-1]),

Hence in total before arr[i,j] there are (i(i-1)/2 + j-1) elements and those elements will have indexes

1 to (i(i-1)/2 + j-1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have index i(i-1)/2 + j in this new single dimensional compact array. Answer C.

0

@ Sourav Basu Can you please elaborate the below lines

1 to (i(i-1)/2 + j-1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have index i(i-1)/2 + j in this new single dimensional compact array. Answer C.

1 to (i(i-1)/2 + j-1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have index i(i-1)/2 + j in this new single dimensional compact array. Answer C.

0

@sutanay3

In this new compact representation, (i,j) th element of the old lower triangular matrix will have (i(i-1)/2 + j-1) elements

before it so, it's own index will be (i(i-1)/2 + j-1) + 1.

It's like if you are standing in a queue and there are 9 people standing before you then, your own position from the starting of the queue will be 10.

In this new compact representation, (i,j) th element of the old lower triangular matrix will have (i(i-1)/2 + j-1) elements

before it so, it's own index will be (i(i-1)/2 + j-1) + 1.

It's like if you are standing in a queue and there are 9 people standing before you then, your own position from the starting of the queue will be 10.

59 votes

Best answer

$j-1 + i(i-1)/2$ ... because if you form a lower triangular matrix it contains elements in rows $1,2,3,...$

So, **C** is the correct answer.

PS: Though not mentioned in question, from options it is clear that **array index starts from 1 and not 0**.

Explanation :

In a lower triangular matrix, $i^{th}$ row contains $(i +1)$ number of non zero elements.

If we assume Array index starting from $1$ then, $i^{th}$ row contains i number of non zero elements.

before $i^{th}$ row there are $i -1$ rows (row $1$ to $i-1$) , and in total these rows has $1+2+3.....+(i-1)= i((i-1)/2$ elements(row $1$ has $1$ element, row $2$ has $2$ elements, .... row $i-1$ has $i-1$ elements etc.)

Now, at $i^{th}$ row, before $j^{th}$ element there are $(j-1)$ elements(starting from $arr[i,1]$ to $arr[i,j-1]$) .

Henc,e in total before $arr[i,j]$ there are $(i(i-1)/2 + j-1)$ elements and those elements will have indexes .

S,o the index of the $(i,j)^{th}$ element of the lower triangular matrix in this new representation is $(j-1) + i(i-1)/2$ which is option **C** .

2

Can You please tell me why it is not j + i(i+1)/2 . Array index should start with 0 generally rgt? So to get A[2][1] , 2 rows have to be crossed, so (1+2) elements in lower triangular matrix and then j. So am having a doubt here, how i(i-1)/2, it should be i(i+1)/2 rgt? Please help me in my doubt. ThankYou..

0

Can u plz explain this sum logic once again , we should be summing up the columns , why rows ?Although calculations are fine but still logic is confusing me ,plz clarify this .

4

if we want a(3,2) from the array below

then row number of 1D array will be $2+\frac{(3\times 2)}{2}=5$

which is correct

1

Please clarify on 2 things:

1. Which index to start 0(zero) or 1(one)? In both place : Matrix and memory

2. Made easy booklet, C option seems to be different compared to gateoverflow options. So which are correct option and correct answer with respect to correct selection of index in every case?

Note : Please describe memory visualization of given scenario of question. It will be helpful a lot.

Please share your views and make solution with no conflicts.

Thanks GO.

1. Which index to start 0(zero) or 1(one)? In both place : Matrix and memory

2. Made easy booklet, C option seems to be different compared to gateoverflow options. So which are correct option and correct answer with respect to correct selection of index in every case?

Note : Please describe memory visualization of given scenario of question. It will be helpful a lot.

Please share your views and make solution with no conflicts.

Thanks GO.

0

means?

Actually I think it is a simple question like from starting what is the xth number non zero element of 2D array, if we represent it in 1D array. Isnot it @Ahwan

Actually I think it is a simple question like from starting what is the xth number non zero element of 2D array, if we represent it in 1D array. Isnot it @Ahwan

2

@srestha what I said is.. Draw a lower triangular 2D array with index starting from one. Then in 1D array.. Start from one too. Do not write the zeros... Option C satisfied. Yes simple one.

0

@srestha How the row number is 5 if we take array index starting from 1.Mine it is coming to be 4. Please explain.

3

@srestha Yes but in the previous comment ,it is told to start both 1D array and 2D array with 1 . Actually I think it should be j instead of (j-1). http://gateforum.com/wp-content/uploads/2013/01/CS-1994.pdf

Or we can start 1 with the matrix and 0 with the 1D array. Then we will get the desired answer.

Or we can start 1 with the matrix and 0 with the 1D array. Then we will get the desired answer.

8

The answer should be j + i*(i -1)/2. The reason is that the returned formula gives the index for the element (i,j -1), we should have added j directly. This question came in ISRO 17 paper too.

3

According to the explanation there will be (j-1)+i*(i-1)/2 elements before the element (i,j), now if our single dimension array also starts with index 1 then the index of (i,j)th element in the single dimension array formed will be j+i*(i-1)/2 and if the index starts with index 0 then the index will be (j-1)+i*(i-1)/2. I think the question needs more clear explanation.

0

(d) is the correct option not (c). Take 3*3 lower triangular matrix and try to eliminate the option then you will get option (d) as correct option.

0

Why did u consider all elements in the ith row. We have to take only those elements which are part of lower triangular matrix. So it should be A[i,i], A[i,i+1],.........,A[i, j]. So we should add only j-i+1 to i(i-1)/2.

0

@ Bhagirath

Awesome explanation, Thank you very much. It's been a long time I was searching for a good explanation. 😊

16 votes

11 votes

option (c)

Explanation:

An example of lower triangular matrix of size 3 x 3 is given below.

1 0 0

2 3 0

4 5 6

While storing we will store as 1 2 3 4 5 6.

Index of the (i,j)th element = the number of elements in (i - 1) rows + j

= (1 + 2 + ... + i-1) + j

= [i(i-1)/2] + j

Hence option (c)

Note:

* The number of elements in (i - 1) rows = 1 + 2 + ... + i-1, because first row contains only 1 element, second row contains only 2 elements, third row contains only 3 elements and so on.

* 1 + 2 + ... + n = n(n-1)/2

Explanation:

An example of lower triangular matrix of size 3 x 3 is given below.

1 0 0

2 3 0

4 5 6

While storing we will store as 1 2 3 4 5 6.

Index of the (i,j)th element = the number of elements in (i - 1) rows + j

= (1 + 2 + ... + i-1) + j

= [i(i-1)/2] + j

Hence option (c)

Note:

* The number of elements in (i - 1) rows = 1 + 2 + ... + i-1, because first row contains only 1 element, second row contains only 2 elements, third row contains only 3 elements and so on.

* 1 + 2 + ... + n = n(n-1)/2

7 votes

An example of lower triangular matrix of size 3 x 3 is given below.

1 0 0

2 3 0

4 5 6

While storing we will store as 1 2 3 4 5 6.

Index of the (i,j)th element = the number of elements in (i - 1) rows + j

= (1 + 2 + ... + i-1) + j

= [i(i-1)/2] + j

Hence option (c)

1 0 0

2 3 0

4 5 6

While storing we will store as 1 2 3 4 5 6.

Index of the (i,j)th element = the number of elements in (i - 1) rows + j

= (1 + 2 + ... + i-1) + j

= [i(i-1)/2] + j

Hence option (c)

7 votes

Whole trick to this question is to guess if array start with 1 or zero. As they have not mentioned you have to consider both the cases and then go by the concept of row major.

First case:

if array start with zero then we have to cross n rows and j number of element in the last column. As each row will be containing elements in increasing order like 1st row will contain 1 non zero element. 2 will 2 non zero. So total number of element we have to cross can be represented as the sum of natural numbers.

so if array start with zero you will can get address with i(i+1)/2 + j

similarly if it start with 1 replace i and j with (i-1) and j-1 respectively.

You will get option C.

First case:

if array start with zero then we have to cross n rows and j number of element in the last column. As each row will be containing elements in increasing order like 1st row will contain 1 non zero element. 2 will 2 non zero. So total number of element we have to cross can be represented as the sum of natural numbers.

so if array start with zero you will can get address with i(i+1)/2 + j

similarly if it start with 1 replace i and j with (i-1) and j-1 respectively.

You will get option C.

4 votes

Although best answer contain all information but i want to demonstrate by example lets take one example of 3x3 lower triangular matrix

1 | 0 | 0 |

2 | 3 | 0 |

4 | 5 | 6 |

now above matrix is stored on following basis in new representation

1 | 2 | 3 | 4 | 5 | 6 |

Now to find index of (i,j)th element by assuming that both array representations are starting from 1.

now lets find the location of element (2,2) by all options

A) i+j = 2+2 = 4 (wrong)

B) i+j-1 = 2+2-1 =3 (right) but check for (3,1) and it will give the same answer so (wrong).

C) (j-1) + i(i-1)/2 = 1 + 2.1/2 =2 (wrong)

D) i + j(j-1)/2 = 2 + 2.1/2 =3 (right) check for (3,1) also it will give the same answer so (wrong).

So clearly no option is matching either answer should be **j + i(i-1)/2** or if new array representation will start from 0 then answer will be **C**.

1

In lower triangular matrix we use the elements above of principle diagonals? so how we can say that row 1 contains 1 element row 2 contains 2 elements ..... row n contians n elements... it should be reversed order . please confirm me in each solution everyone is taking LTM means below the principle diagonal.

2

@Divyanshum29, A square matrix is called **lower triangular** if all the entries *above *the main diagonal are zero. So basically in first row there will be one non zero entry and in second row there will be two non zero entry like wise go further.

2 votes

Let Matrix indices are of form 1st row -->11 12 13 14....1n

2nd row--> 21 22 23 23...2n,

Therefore number of non zero elements present in row1 = 1, row 2 =2 , row3 =3 .....row **i = i**

Number of non zero elements before ith row = 1+2+3+.....i-1 = i(i+1)/2

Now array starts from index 0. To store i(i+1)/2 elements in array, indexes used will be {i(i+1)/2} -1 as array starts from 0th index.

Now, we have 'j' more elements to cross to reach(i,j), so the index of (i,j) will be {i(i+1)/2} -1 +j = {i(i+1)/2} +j-1

Therefore Answer is C