GATE CSE 1994 | Question: 1.11

Question

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:

• A. $i+j$
• B. $i+j-1$
• C. $(j-1)+\frac{i(i-1)}{2}$
• D. $i+\frac{j(j-1)}{2}$

Comments

Before looking for solution, use this hint.
Diagonal is (i,j) where i=j. Now try solving it.

---

I’m kinda pissed right now cuz they assumed 1 based indexing for the 2d array(matrix) but they assumed 0 based indexing for the compact array representation. Bravo man almost wasted 40 minutes thinking why the calculation doesn’t work.

---

if question is for upper triangular matrix

   Row and Col start from 1

     j               1                                2                             3       

       0             1                  2               3                4               5

1	2	3	5	6	9

then ans :

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

(i,j)=(1,3)=i-1 +ceil[(i*j)/2]=1-1+ceil[(1*3)/2]=0+ceil[1.5]=0+2=2=2's index of array 

Answer 1

$\begin{bmatrix} (0,0)& (0,1)& (0,2)& (0,3)\\ (1,0)& (1,1)& (1,2)& (1,3)\\ (2,0)& (2,1)& (2,2)& (2,3)\\ (3,0)& (3,1)& (3,2)& (3,3) \end{bmatrix}$

 

1D array for lower triangular matrix : $\begin{bmatrix} (0,0) & (1,0) & (1,1) & (2,0) & (2,1) & (2,2) & (3,0) & (3,1) & (3,2) &(3,3) \end{bmatrix}$

 

Now check for options:

index=3 i.e. (2,0) doesn't satisfy option A (index=i+j)

index=0 i.e. (0,0) doesn't satisfy option B (index=i+j-1)

index=0 i.e. (0,0) doesn't satisfy option c (index=ij-1+i(i-1)/2)

index=2 i.e. (1,1) doesn't satisfy option B (index=i+j(j-1)/2)

 

i think no options are correct