# Get number of elements of a square matrix given a vector that has upper right elements of that matrix

Suppose I have some vectors:

• $[1,2,1]$ its length is $3$ wich represents a matrix like $\begin{pmatrix} 1 & 2\\ -1 & 1 \end{pmatrix}$ the complete matrix would have $4$ elements

• $[1,2,1,3,4,1]$ its length is $6$ wich represents $\begin{pmatrix} 1& 2& 3\\ -1& 1 & 4\\ -1& -1 &1 \end{pmatrix}$ the complete matrix would have $9$ elements

• $[1,2,1,3,4,1,5,6,7,1]$ its length is $10$ wich represents $\begin{pmatrix} 1 & 2& 3& 5\\ -1 &1 & 4& 6\\ -1 &-1 &1 & 7\\ -1 &-1 &-1 &1 \end{pmatrix}$ the complete matrix would have $16$ elements

• $[1,2,1,3,4,1,5,6,7,1,8,9,10,11,1]$ its length is $15$ wich represents

$\begin{pmatrix} 1 &2 &3 &5 &8 \\ -1 &1 &4 &6 &9 \\ -1 &-1 &1 &7 &10 \\ -1 &-1 &-1 &1 &11 \\ -1 &-1 &-1 &-1 &-1 \end{pmatrix}$ the complete matrix would have $25$ elements

How do I find a general formula to get all elements of a square matrix from the number of elements in a vector?

So

• $3\to 4$
• $6\to 9$
• $10\to 16$
• $15\to 25$
• etc...

also: How would you know the matrix size $2\times 2$, $3\times 3$,...$n\times n$?

-
If you can use the floor function, a formula is $n\mapsto (\lfloor\sqrt{2n}\rfloor)^2$ – Jonas Meyer Aug 5 '11 at 20:34
That is a good one, How did you get to this formula? – cMinor Aug 5 '11 at 20:41
cMinor: I posted it as an answer with explanation. – Jonas Meyer Aug 5 '11 at 20:50

Notice that all of your matrices are $n^2$ in size, where $n$ is the number of rows (or columns), and all of your vectors are 1+2+3+...+n = $n(n+1)/2$ in size. Your function takes numbers $n(n+1)/2$ to $n^2$, where $n$ is an integer. If you want to know what $n$ is from the length of your vector, just solve the quadratic equation: e.g. if your vector is 15 in length, solve n(n+1)/2 = 15. You get n = 5 or n = -6, and you should obviously disregard the latter because it's negative. Then you can square 5 to get the size of your matrix.

Alternatively: 3, 6, 10, 15, ... are the numbers of elements in the upper right of your matrix, including the diagonal. These elements (marked with a star below) form a 'triangle' shape in your matrix, of side length 2, 3, 4, 5 respectively:

$\underbrace{\begin{pmatrix} *&*&*&*&* \\ &*&*&*&* \\ &&*&*&* \\ &&&*&* \\ &&&&* \end{pmatrix}}_{\text{length }5}$

The "missing" elements in the lower left ('marked' as a blank space above) form another slightly smaller 'triangle' shape of size 1, 2, 3, 4 etc. respectively - that is, the lower left has 1, 3, 6, 10, ... elements in it.

These are obviously the same sequence, just shifted along by 1: that is, the upper right of a matrix of side length 10 (with the diagonal) will have as many elements as the lower left of a matrix of side length 11 (without the diagonal). So to get the total number of elements in your matrix, just add the number in the upper right to the number in the lower left: 3+1, 6+3, 10+6, 15+10, ... In recurrence relation speak, if $n_i$ is the number of elements in your vector, the number of elements in your matrix is $n_{i-1} + n_i$.

-

The function $n\mapsto \frac12 ( 1 + 4 n - \sqrt{1+8n})$ does the job.

-
Could you explain why is that? – cMinor Aug 5 '11 at 20:39

As Billy explains, you can find an explicit formula by solving a quadratic, the result of which appears in Fabian's answer.

An alternative is to note that $$\frac{m^2}{2}\lt\frac{m(m+1)}{2}\lt\frac{(m+1)^2}{2}.$$ You are given $n=\frac{m(m+1)}{2}$, and you want $m^2$. The inequalities above yield $$m^2<2n<(m+1)^2,$$ so $$m<\sqrt{2n}<m+1.$$ This implies that $m=\lfloor\sqrt{2n}\rfloor$ (the greatest integer not greater than $\sqrt{2n}$). Finally, if the vector has $n$ entries, then the matrix has $\lfloor\sqrt{2n}\rfloor^2$ entries.

-