7.3 Symmetric Matrix Data Structures

Recognizing the special character of symmetric matrices can save time and storage during the solution of linear systems. More specifically, a dense matrix requires storage for n2 elements. A symmetric matrix can be stored in about half the space, n2+n2\frac{{n}^{2}+n}{2} elements. Only the upper (or lower) triangular portion of A has to be explicitly stored. The implicit portions of A can be retrieved using Equation 57. An efficient data structure for storing dense, symmetric matrices is a simple linear array. If the upper triangular portion of A is retained, the array is organized in the following manner.

𝐀=(a11,a12,,a1n,a21,,a2n,,ann)\mathbf{A}=({a}_{11},{a}_{12},\cdots,{a}_{1n},{a}_{21},\cdots,{a}_{2n},\cdots,% {a}_{nn}) (66)

The element aij{}_{ij} is retrieved from the linear array by the following indexing rule.

aij=𝐚[(i-1)(n)-(i-1)i/2+j]a_{ij}=\mathbf{a}\text{[}(i-1)(n)-(i-1)i/2+j\text{]} (67)

If array and matrix indexing is zero based (as in the C programming language), the subscripting rule becomes

aij=𝐚[in-(i-1)i/2+j]a_{ij}=\mathbf{a}\text{[}in-(i-1)i/2+j\text{]} (68)

If the lower triangular portion of A is retained, the linear array is organized as follows.

𝐀=(a11,a21,a22,a31,,an1,an2,,ann)\mathbf{A}=({a}_{11},{a}_{21},{a}_{22},{a}_{31},\cdots,{a}_{n1},{a}_{n2},% \cdots,{a}_{nn}) (69)

The element aij is retrieved from the linear array by the following indexing rule.

aij=𝐚[i(i-1)/2+j]a_{ij}=\mathbf{a}\text{[}i(i-1)/2+j\text{]} (70)

If array and matrix subscripts are zero based, Equation 70 becomes

aij=𝐚[i(i+1)/2+j]a_{ij}=\mathbf{a}\text{[}i(i+1)/2+j\text{]} (71)

You will observe that the dimension of A does not enter the indexing calculation when its lower triangular portion is retained. The indexing equations are implemented most efficiently by replacing division by two with a right shift.