Pivots, rank, singularity, determinant, positive definiteness

Pivots

Now that we have the method of elimination, we can get a lot of information about a matrix easily. The pivots of a matrix are the first non-zero numbers sitting in each row of U after elimination. Here we return those pivots along with the columns in which they were found:

def pivots(self):
    _, _, _, U, _, _ = self.elimination()
    # extract the first non-zero from each row - track the column number
    U = U.tr()
    pivots = {}
    found = []
    for j, col in enumerate(U.data):
        piv_pos = sum(list(map(bool, col)))
        if piv_pos not in found:
            found.append(piv_pos)
            pivots[j] = col[piv_pos-1]
    return pivots

Demo

We create two matrices, call the pivots method and print the results:

import linalg as la

A = la.Mat([[4, 2, 4],
            [0, 3, 3],
            [0, 1, 2]])

B = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 7, 9]])

print(A.pivots())

print(B.pivots())

Outputs:

>>> print(A_pivots)
{0: 4.0, 1: 3.0, 2: 1.0}

>>> print(B_pivots)
{0: 1.0, 1: -3.0}

Rank

The rank of a matrix tells us a huge amount, and is simply the number of pivots:

def rank(self):
    return len(self.pivots())

Demo

We create two matrices, call the rank method and print the results:

A = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 8, 9]])

B = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 7, 9]])

A_rank = A.rank()

B_rank = B.rank()

print(A_rank)
print()
print(B_rank)

Outputs:

>>> print(A_rank)
3

>>> print(B_rank)
2

Singularity

The matrix is singular if during elimination row exchanges can't avoid a zero in a pivot position. Our elimination method already returns a variable indicating singularity, and so this next method just provides a cleaner way of accessing that variable:

def is_singular(self):
    _, _, _, _, singular, _ = self.elimination()
    return singular

Demo

We create two matrices, call the is_singular method and print the results:

A = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 8, 9]])

B = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 7, 9]])

A_sing = A.is_singular()

B_sing = B.is_singular()

print(A_sing)
print()
print(B_sing)

Outputs:

>>> print(A_sing)
0
>>> print(B_sing)
1

Determinant

The determinant of a matrix is simply the product of the pivots, with a negative sign if there were an odd number of row exchanges. Here we don't use the pivot method we wrote, as we also need the number of row exchanges:

def determinant(self):
    # find U
    _, _, _, U, _, row_exchange_count = self.elimination()
    # muliply the pivots
    det = 1
    diag_vals = U.diag()
    for val in diag_vals:
        det *= val
    # if an odd number of row exchanges, multiply determinant by minus one
    if row_exchange_count % 2:
        det *= -1
    return det

Demo

We create two matrices, call the determinant method and print the results:

A = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 8, 9]])

B = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 7, 9]])

A_determinant = A.determinant()

B_determinant = B.determinant()

print(A_determinant)
print()
print(B_determinant)

Outputs:

>>> print(A_determinant)
6.0

>>> print(B_determinant)
-0.0

Is matrix positive definite?

If all the pivots of a matrix are strictly greater than zero, then the matrix is positive definite. If they are greater than or equal to zero, then the matrix is positive semi-definite. Similary, strictly less than zero means the matrix is negative definite and if there are also some zeros then the matrix is negative semi-definite.

Code implementation

We also create a method that returns the base-10 integer representation of a base-2 (i.e. binary) number. The binary number is constructed from the TRUE/FALSE answers to 3 queries: whether the matrix contains any negative, zero (i.e less pivots than columns), or positive pivots. The answers to these 3 queries uniquely determine what kind of 'definiteness' (if any) we can call the matrix. Thus the method returns a number (between 0 and 7: since $2^3 = 8$ possibilities) which can be used as a unique identifier of the 'definiteness':

def pivot_sign_code(self):
    '''Returns number between 0 and 7 according to signs of pivots. We do
    this by constructing a 3-bit binary number, where each bit represents
    the presence/absence of negative, zero, or positive pivots, and then
    converting from binary to a base 10 integer.'''
    pivot_info = self.pivots().items()

    neg = int(any(piv[1] < 0 for piv in pivot_info))
    semi = int(len(pivot_info) < self.size(1))
    pos = int(any(piv[1] > 0 for piv in pivot_info))

    return int(str(neg) + str(semi) + str(pos), 2)

def is_negdef(self):
    return self.pivot_sign_code() == 4

def is_negsemidef(self):
    return self.pivot_sign_code() == 6

def is_possemidef(self):
    return self.pivot_sign_code() == 3

def is_posdef(self):
    return self.pivot_sign_code() == 1

Demo

We use the same matrices as in the Pivots section above , and call the pivots method and check if they positive definite:

import linalg as la

A = la.Mat([[4, 2, 4],
            [0, 3, 3],
            [0, 1, 2]])

B = la.Mat([[1, 2, 3],
            [4, 5, 6],
            [5, 7, 9]])

print(A.pivots())
A.is_posdef()

print(B.pivots())
B.is_posdef()

Outputs:

>>> print(A_pivots)
{0: 4.0, 1: 3.0, 2: 1.0}

>>> A.is_posdef()
True

>>> print(B_pivots)
{0: 1.0, 1: -3.0}

>>> B.is_posdef()
False

< Back substitution

Inverse >

back to project main page
back to home

---