RankRizz
JEE MAIN 2018 · 16 APR ONLINE+4 / −1MEDIUMTRANSCRIBED

JEE Main 2018 Mathematics question — Matrix multiplication, powers and matrix equations

Let A=[100110111]A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} and B=A20B = A^{20}. Then the sum of the elements of the first column of B is:

SOLUTION

We have the lower-triangular matrix

A=[100110111]A=\begin{bmatrix}1&0&0\\1&1&0\\1&1&1\end{bmatrix}

and we want the sum of the three numbers that appear in the first column of B=A20 .B=A^{20}\,. Let us denote, for every positive integer n,n,

An=[a11(n)a12(n)a13(n)a21(n)a22(n)a23(n)a31(n)a32(n)a33(n)].A^{n}=\begin{bmatrix}a_{11}^{(n)}&a_{12}^{(n)}&a_{13}^{(n)}\\[2pt] a_{21}^{(n)}&a_{22}^{(n)}&a_{23}^{(n)}\\[2pt] a_{31}^{(n)}&a_{32}^{(n)}&a_{33}^{(n)}\end{bmatrix}.

The required sum is therefore

Sn=a11(n)+a21(n)+a31(n).S_{n}=a_{11}^{(n)}+a_{21}^{(n)}+a_{31}^{(n)}.

We now build up the powers step by step so that every algebraic detail is visible and a pattern can be recognised.

Power 1. We clearly have

A1=A=[100110111],A^{1}=A=\begin{bmatrix}1&0&0\\1&1&0\\1&1&1\end{bmatrix},

so

(a11(1), a21(1), a31(1))=(1,1,1)\bigl(a_{11}^{(1)},\,a_{21}^{(1)},\,a_{31}^{(1)}\bigr)=(1,1,1)

and therefore

S1=1+1+1=3.S_{1}=1+1+1=3.

Power 2. Using plain matrix multiplication, and writing every scalar product explicitly, we have

A2=A ⁣⋅ ⁣A=[1⋅1+0⋅1+0⋅11⋅0+0⋅1+0⋅11⋅0+0⋅0+0⋅11⋅1+1⋅1+0⋅11⋅0+1⋅1+0⋅11⋅0+1⋅0+0⋅11⋅1+1⋅1+1⋅11⋅0+1⋅1+1⋅11⋅0+1⋅0+1⋅1]A^{2}=A\!\cdot\!A=\begin{bmatrix} 1\cdot1+0\cdot1+0\cdot1 & 1\cdot0+0\cdot1+0\cdot1 & 1\cdot0+0\cdot0+0\cdot1\\[4pt] 1\cdot1+1\cdot1+0\cdot1 & 1\cdot0+1\cdot1+0\cdot1 & 1\cdot0+1\cdot0+0\cdot1\\[4pt] 1\cdot1+1\cdot1+1\cdot1 & 1\cdot0+1\cdot1+1\cdot1 & 1\cdot0+1\cdot0+1\cdot1 \end{bmatrix}

which simplifies to

A2=[100210321].A^{2}=\begin{bmatrix}1&0&0\\2&1&0\\3&2&1\end{bmatrix}.

Thus

(a11(2), a21(2), a31(2))=(1,2,3)\bigl(a_{11}^{(2)},\,a_{21}^{(2)},\,a_{31}^{(2)}\bigr)=(1,2,3)

and

S2=1+2+3=6.S_{2}=1+2+3=6.

Power 3. Multiplying A2A^{2} by AA again, while displaying every dot product,

A3=A2A=[100210321][100110111]A^{3}=A^{2}A=\begin{bmatrix} 1&0&0\\2&1&0\\3&2&1\end{bmatrix} \begin{bmatrix} 1&0&0\\1&1&0\\1&1&1 \end{bmatrix}

gives

A3=[1⋅1+0⋅1+0⋅11⋅0+0⋅1+0⋅11⋅0+0⋅0+0⋅12⋅1+1⋅1+0⋅12⋅0+1⋅1+0⋅12⋅0+1⋅0+0⋅13⋅1+2⋅1+1⋅13⋅0+2⋅1+1⋅13⋅0+2⋅0+1⋅1]=[100310631].\begin{aligned} A^{3}&=\begin{bmatrix} 1\cdot1+0\cdot1+0\cdot1 & 1\cdot0+0\cdot1+0\cdot1 & 1\cdot0+0\cdot0+0\cdot1\\[4pt] 2\cdot1+1\cdot1+0\cdot1 & 2\cdot0+1\cdot1+0\cdot1 & 2\cdot0+1\cdot0+0\cdot1\\[4pt] 3\cdot1+2\cdot1+1\cdot1 & 3\cdot0+2\cdot1+1\cdot1 & 3\cdot0+2\cdot0+1\cdot1 \end{bmatrix}\\[6pt] &=\begin{bmatrix}1&0&0\\3&1&0\\6&3&1\end{bmatrix}. \end{aligned}

Hence

(a11(3), a21(3), a31(3))=(1,3,6)\bigl(a_{11}^{(3)},\,a_{21}^{(3)},\,a_{31}^{(3)}\bigr)=(1,3,6)

and

S3=1+3+6=10.S_{3}=1+3+6=10.

Writing the sums that we have found so far, we notice the sequence

S1=3,S2=6,S3=10.S_{1}=3,\qquad S_{2}=6,\qquad S_{3}=10.

The successive differences are 33 and 4,4, then 44 and ?? in the next step, so it looks like the pattern is the familiar triangular-number pattern. Indeed, the first three terms can be matched exactly by the well-known formula for the kk-th triangular number, namely

Tk=k(k+1)2.T_{k}=\frac{k(k+1)}{2}.

Re-indexing appropriately, we suspect that

Sn=(n+1)(n+2)2=(n+22).S_{n}=\frac{(n+1)(n+2)}{2}=\binom{n+2}{2}.

Formal proof of the pattern by mathematical induction.

Base case n=1n=1 has already been calculated: S1=3=(32).S_{1}=3=\binom{3}{2}. Now assume for some n=kn=k that

Sk=a11(k)+a21(k)+a31(k)=(k+22).S_{k}=a_{11}^{(k)}+a_{21}^{(k)}+a_{31}^{(k)}=\binom{k+2}{2}.

To pass from AkA^{k} to Ak+1,A^{k+1}, we right-multiply by A.A. Concerning only the first column, we use the fact that the first column of AA itself is

[111],\begin{bmatrix}1\\1\\1\end{bmatrix},

so

[a11(k+1)a21(k+1)a31(k+1)]=Ak[111]=[a11(k)⋅1+a12(k)⋅1+a13(k)⋅1a21(k)⋅1+a22(k)⋅1+a23(k)⋅1a31(k)⋅1+a32(k)⋅1+a33(k)⋅1].\begin{bmatrix}a_{11}^{(k+1)}\\ a_{21}^{(k+1)}\\ a_{31}^{(k+1)}\end{bmatrix}=A^{k}\begin{bmatrix}1\\1\\1\end{bmatrix}= \begin{bmatrix} a_{11}^{(k)}\cdot1+a_{12}^{(k)}\cdot1+a_{13}^{(k)}\cdot1\\[4pt] a_{21}^{(k)}\cdot1+a_{22}^{(k)}\cdot1+a_{23}^{(k)}\cdot1\\[4pt] a_{31}^{(k)}\cdot1+a_{32}^{(k)}\cdot1+a_{33}^{(k)}\cdot1 \end{bmatrix}.

That is,

a11(k+1)=a11(k)+a12(k)+a13(k),a21(k+1)=a21(k)+a22(k)+a23(k),a31(k+1)=a31(k)+a32(k)+a33(k).\begin{aligned} a_{11}^{(k+1)}&=a_{11}^{(k)}+a_{12}^{(k)}+a_{13}^{(k)},\\ a_{21}^{(k+1)}&=a_{21}^{(k)}+a_{22}^{(k)}+a_{23}^{(k)},\\ a_{31}^{(k+1)}&=a_{31}^{(k)}+a_{32}^{(k)}+a_{33}^{(k)}. \end{aligned}

Adding these three equalities together we get

Sk+1=Sk+(a12(k)+a22(k)+a32(k))+(a13(k)+a23(k)+a33(k)).S_{k+1}=S_{k}+ \bigl(a_{12}^{(k)}+a_{22}^{(k)}+a_{32}^{(k)}\bigr)+ \bigl(a_{13}^{(k)}+a_{23}^{(k)}+a_{33}^{(k)}\bigr).

But AkA^{k} is lower triangular with ones on the diagonal, so a12(k)=0a_{12}^{(k)}=0 and a13(k)=a23(k)=0.a_{13}^{(k)}=a_{23}^{(k)}=0. Therefore

Sk+1=Sk+a22(k)+a32(k)+a33(k).S_{k+1}=S_{k}+a_{22}^{(k)}+a_{32}^{(k)}+a_{33}^{(k)}.

Since every diagonal entry of any power of a unit lower-triangular matrix is 1,1, we know a22(k)=a33(k)=1.a_{22}^{(k)}=a_{33}^{(k)}=1. Furthermore, the (3,2) entry is precisely k,k, because we can check directly for k=1,2,3k=1,2,3 and see by induction that one unit is added at each new multiplication. Hence

Sk+1=Sk+1+k+1=Sk+k+2.S_{k+1}=S_{k}+1+k+1=S_{k}+k+2.

Using the induction hypothesis Sk=(k+1)(k+2)2,S_{k}=\dfrac{(k+1)(k+2)}{2}, we get

Sk+1=(k+1)(k+2)2+k+2=(k+1)(k+2)+2(k+2)2=(k+2)(k+3)2=((k+1)+22).\begin{aligned} S_{k+1}&=\frac{(k+1)(k+2)}{2}+k+2\\[4pt] &=\frac{(k+1)(k+2)+2(k+2)}{2}\\[4pt] &=\frac{(k+2)(k+3)}{2}\\[4pt] &=\binom{(k+1)+2}{2}. \end{aligned}

Thus the induction is complete and the formula

Sn=(n+1)(n+2)2=(n+22)S_{n}=\frac{(n+1)(n+2)}{2}=\binom{n+2}{2}

holds for every positive integer n.n.

Evaluating for n=20.n=20.

Substituting n=20n=20 in the proven expression, we obtain

S20=(20+1)(20+2)2=21⋅222=231.S_{20}=\frac{(20+1)(20+2)}{2}=\frac{21\cdot22}{2}=231.

Therefore, the sum of the elements of the first column of B=A20B=A^{20} equals 231.231.

Hence, the correct answer is Option D.

Tagged Matrix multiplication, powers and matrix equations. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicMatrix multiplication, powers and matrix equations
TypeMultiple choice