In many branches of engineering and science it is desirable to be able to mathematically determine the state of a system based on a set of physical relationships. These physical relationships may be determined from characteristics such as circuit topology, mass, weight, or force to name a few. For example, the injected currents, network topology, and branch impedances govern the voltages at each node of a circuit. In many cases, the relationship between the known, or input, quantities and the unknown, or output, states is a linear relationship. Therefore, a linear system may be generically modeled as

Ax = b (2.1)

where b is the n× 1 vector of known quantities, x is the n× 1 unknown state vector, and A is the n × n matrix that relates x to b. For the time being, it will be assumed that the matrix A is invertible, or non-singular; thus, each vector b will yield a unique corresponding vector x. Thus the matrix A−1

exists and x∗ = A−1b (2.2)

is the unique solution to equation (2.1). The natural approach to solving equation (2.1) is to directly calculate the

inverse of A and multiply it by the vector b. One method to calculate A−1 is to use Cramer’s rule :

A−1(i, j) = 1

det(A) (Aij)

T for i = 1, . . . , n, j = 1, . . . , n (2.3)

where A−1(i, j) is the ijth entry of A−1 and Aij is the cofactor of each entry aij of A. This method requires the calculation of (n+ 1) determinants which results in 2(n + 1)! multiplications to ﬁnd A−1! For large values of n, the calculation requirement grows too rapidly for computational tractability; thus, alternative approaches have been developed.