# Calculating number of non-zero elements in a lower triangular matrix

Given a lower triangular matrix $M$ of size $m$ by $n$, is there an equation for the number of elements in this matrix that can be non-zero? What if the matrix is strictly lower triangular?

• Are you asking for the number of elements that can (as opposed to 'are') be non-zero? Commented Nov 6, 2012 at 19:10
• @amWhy I don't think there's a problem. Many people take triangular matrices to simply be matrices which are all zero above or below the main diagonal.
– EuYu
Commented Nov 6, 2012 at 19:11
• Try $\frac{1}{2}(\min(m,n)(\min(m,n)+1))+ n \min(m-n,0)$. Commented Nov 6, 2012 at 19:16
• @EuYu I deleted my comment; it's probably my issue (triangular only if square)...a non-square triangular matrix just sort of clashes with my intuition! Commented Nov 6, 2012 at 19:18
• @amWhy We should call them "right-trapezoidal" matrices!
– EuYu
Commented Nov 6, 2012 at 19:22

It is possible to calculate the number of the maximum amount of non-zero elements in a lower (or upper) triangular matrix.

The simplest way to do it is to write a $N\times N$ matrix:

$$\mathbb{A}=\left[\begin{array}{cccc} a_{1,1}&a_{1,2}&\cdots&a_{1,N}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,N}\\ \vdots&\vdots&\vdots&\vdots\\ a_{N,1}&a_{N,2}&\cdots&a_{N,N}\\ \end{array}\right],$$

and notice that for a lower triangular matrix, the non-zero elements $a_{i,j}$ have $i\geq j$. Thus, the indices of the non-zero elements are identified by the unique ordered pairs, $(i,j)$, with $i\in[1,N]$ and $j\in[1,N]$, such that $i\geq j$.

So you have the pairs:

$$\overbrace{(1,1)}^{1 pair}\\ \overbrace{(2,1)\ (2,2)}^{2 pairs}\\ \vdots\\ \overbrace{(N,1)\ (N,2)\ \cdots\ (N,N)}^{N pairs},$$

and the amount of non-zero elements, $E$, is exactly the amount of unique pairs you have. Now you just have to sum:

$$E=\sum\limits_{n=1}^{N}n=\dfrac{\left(1+N\right)N}{2}$$

• Great answer; what makes this answer particularly appealing is that the summation is very intuitive. Commented Jul 19, 2014 at 16:38
• yes, but only then I noticed you actually wanted it for a $m\times n$ matrix. There a comment in your question which generalizes the formula I worked out, considering the square part (and thus triangular part) of the general $m\times n$ matrix. Commented Jul 20, 2014 at 16:51

My colleague (kudos to him) and I discussed the parallels for counting the elements in a triangular matrix to a combination.

Given that you do not want to include the main diagonal in your count, you can simply express this as a combination, as you want to find all possible combinations of 2 elements (bar the combination of an element with itself):

$${n \choose k}=\frac{n!}{k!(n-k)!}$$

So for the case of $k=2$, this will be:

$$\frac{n!}{2!(n-2)!}$$

...which nicely reduces down to:

$$\frac{n!}{2!(n-2)!}$$ $$=\frac{1}{2!}\cdot\frac{n!}{(n-2)!}$$ $$=\frac{1}{2}\cdot n(n-1)$$ $$=\frac{n(n-1)}{2}$$

For the reduction from $\frac{n!}{(n-2)!}$ to $n(n-1)$, think of:

$$\require{cancel} \frac{4!}{(4-2)!} = \frac{4\cdot3\cdot \cancel{2\cdot1}}{\cancel{2\cdot1}}=12$$

...which leaves you essentially with $n(n-1)$.

This is similar to result of Girardi's answer, with the exception of leaving out all elements of the main diagonal.

• That's great; thank you for pointing this out. Commented Jan 23, 2015 at 15:45

In case your matrix is lower triangular It is a square matrix.

I agree with @copper.hat 37 comment. The number of non-zero entries isn't determenistic. As long as all the entries above the main diagonal are zeros you can put a zero wherever you want and therefore It can be changed.

For example for two 3x3 lower triangular matrices : \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}

you have different number of non-zeors entries.

It is possible though, to calculate the minimum number of zeros of a lower triangular matrix. In order to do so you just have to understand how's the number of elements above the main diagonal grows, these must be zeros.

For example 3x3, 4x4, 5x5:

\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 \end{bmatrix}

\begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{bmatrix}

If you count how much zeros (minimum case) you have, you'll get 3,6,10 respectively to the matrices above.

If this is the case a fourmla can be extracted.

Hope It helps =]

• Yes, this helps to shed light on the issue. Thank you. Commented Nov 6, 2012 at 20:16
• No problem. If there's anything else you need clarification let me know. Commented Nov 6, 2012 at 20:21

I personally like Girardis Solution. The same solution can be derived (motivated by the answer of victor_v) by appling k-combination with repetitions. This allows to include the elements in the diagonal.

$$\binom{n+k-1}{k} = \frac{(n+k-1)!}{k!(n-1)!},$$ where in this case $$k=2$$ and $$n=N$$, so $$E = \frac{(n+1)!}{2!(n-1)!} = \frac{(n+1)n}{2}$$

• This is an excellent motivation. Commented Jun 10, 2020 at 14:25

I think there is no straight forward way ,but you can deal this matrix as a sparse matrix and there is a numerical solutions to find the sparseness of the matrix.

Note that :sparse matrix is a matrix in which most of the elements are zero. By contrast, if most of the elements are nonzero, then the matrix is considered dense.