# GATE1994-1.11

9k views

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:

1. $i+j$
2. $i+j-1$
3. $(j-1)+\frac{i(i-1)}{2}$
4. $i+\frac{j(j-1)}{2}$
in DS
edited
0
0
Could anyone explain it clearly by giving one example without any ambiguity ?
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.
0
@Bikram sir pls give example for this
0
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.
0
Fix this please or mention in question somewhere it's wrong. Wasted an hour of mine
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.
0
'Elements of the lower triangular matrix', what do they mean by this ?  Should it be the elements below the principal diagonal ? or should we include the diagonal elements too. Because if we don't include the diagonal elements, the answer comes out to be i+j-1.
0
What would be the ans if question is for upper triangular matrix
1
$a[1....n][1....n]$

$Loc[i][j]$

$\\ =\left \{\underbrace {i-1}+(j-1) \right \}$

$Natural\ \#\ sum\\ of\ (i-1)\ rows$

$=\dfrac{(i-1)\times i}{2}\ +\ (j-1)$

$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 .

edited
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 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 .
0
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

0
@srestha Why do you assume that array index starts from 1 and not 0?
1
it is more close to option
1

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.

Thanks GO.
3
@srestha I guess it is working only when in both cases array index starts from 1.
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
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
yes ..
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.
0
yes, but we never start array index from 1
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.
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.
3 Hence, Option C is the answer.

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

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

answer is C...... it is (j-1) + i(i-1)/2  when indices start from 1 ( as we guess from the options )

edited by
17
1
What will be the expression for column major ??
0
here  i= row and j= column right?
0 help me guys can't able to get formula how can we generate it formula?

(j-1) + i(i-1)/2 ???????????/how

0
plzz explain wid an exmaple..m unable 2 understand..i have doubts in arrays..
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
0
although, I agree with you but option c contains : (j-1) + i(i-1)/2
your answer would be true if matrix have indexing starting from zero,i guess (still confuse although)
0
Option updated . It is to be assumed that indexing starts from 1
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)
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.

similarly if it start with 1 replace i and j with (i-1) and j-1 respectively.
You will get option C.

Option C in actual gate paper is correct. See the explanation below.

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.

1
got it thanks

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

0
i think it should be {i(i-1)/2} +j-1 instead of {i(i+1)/2} +j-1

by the way nice explanation.

## Related questions

1
1.3k views
An array $A$ contains $n$ integers in non-decreasing order, $A \leq A \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $i, j,$ such that $A[i]+A[j]=a$ given integer $M$, if such $i, j$ exist.
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $\text{1, 2, 3, 4, 5}$ in that order? $\text{3, 4, 5, 1, 2}$ $\text{3, 4, 5, 2, 1}$ $\text{1, 5, 2, 3, 4}$ $\text{5, 4, 3, 1, 2}$
A queue $Q$ containing $n$ items and an empty stack $S$ are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the TOP of the stack, and the order of all other items are ... operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.