det_of_minor

View page source

Determinant of a Minor

Syntax

# include <cppad/speed/det_of_minor.hpp>
d = det_of_minor ( a , m , n , r , c )

Prototype

template <class Scalar>
Scalar det_of_minor(
   const std::vector<Scalar>&      a  ,
   size_t                          m  ,
   size_t                          n  ,
   std::vector<size_t>&            r  ,
   std::vector<size_t>&            c  )
{  assert( a.size() == m * m );
   assert( r.size() == m + 1 );
   assert( c.size() == m + 1 );

Inclusion

The template function det_of_minor is defined in the CppAD namespace by including the file cppad/speed/det_of_minor.hpp .

Purpose

This template function returns the determinant of a minor of the matrix \(A\) using expansion by minors. This template function is for example and testing purposes only. Expansion by minors is chosen as an example because it uses a lot of floating point operations yet does not require much source code (on the order of m factorial floating point operations and about 100 lines of source code including comments). This is not an efficient method for computing a determinant; for example, using an LU factorization would be faster.

Minor

The elements of the \(n \times n\) minor \(M\) of the matrix \(A\) are defined, for \(i = 0 , \ldots , n-1\) and \(j = 0 , \ldots , n-1\), by

\[M_{i,j} = A_{R(i), C(j)}\]

where the functions \(R(i)\) is defined by the argument r and \(C(j)\) is defined by the argument c .

Determinant of A

If the following conditions hold, the minor is the entire matrix \(A\) and hence det_of_minor will return the determinant of \(A\):

  1. \(n = m\).

  2. for \(i = 0 , \ldots , m-1\), \(r[i] = i+1\), and \(r[m] = 0\).

  3. for \(j = 0 , \ldots , m-1\), \(c[j] = j+1\), and \(c[m] = 0\).

Scalar

This is the type of the elements of a . If x and y are Scalar objects, the type Scalar must support the following operations:

Syntax

Description

Result Type

Scalar (0)

constructor for Scalar object equal to zero

Scalar

x = y

set value of x to current value of y

x + y

value of x plus y

Scalar

x - y

value of x minus y

Scalar

x * y

value of x times value of y

Scalar

a

The elements of the \(m \times m\) matrix \(A\) are defined, for \(i = 0 , \ldots , m-1\) and \(j = 0 , \ldots , m-1\), by

\[A_{i,j} = a[ i * m + j]\]

m

This is the number of rows (and columns) in the square matrix \(A\).

n

This is the number of rows (and columns) in the square minor \(M\).

r

This defines the function \(R(i)\) which specifies the rows of the minor \(M\). To be specific, the function \(R(i)\) for \(i = 1, \ldots , n-1\) is defined by

\begin{eqnarray} R(0) & = & r[m] \\ R(i) & = & r[ R(i-1) ] \end{eqnarray}

All the elements of r have value less than or equal m ; \(R(i) < m\) and \(r[ R(n-1) ] = m\) . The elements of vector r are modified during the computation, and restored to their original value before the return from det_of_minor .

c

This defines the function \(C(i)\) which specifies the columns of the minor \(M\). To be specific, the function \(C(i)\) for \(j = 1, \ldots , n-1\) is defined by

\begin{eqnarray} C(0) & = & c[m] \\ C(j) & = & c[ C(j-1) ] \end{eqnarray}

All the elements of c must have value less than or equal m ; \(C(j) < m\) and \(c[ C(n-1) ] = m\) . The elements of vector c are modified during the computation, and restored to their original value before the return from det_of_minor .

d

The return value d is equal to the determinant of the minor \(M\).

Example

The file det_of_minor.cpp contains an example and test of det_of_minor.hpp .

Source Code

The file det_of_minor.hpp contains the source for this template function.