# Faddeev-Leverrier Algorithm

A MATLAB implementation of the Faddeev-Leverrier algorithm to compute the coefficients of the characteristic polynomial of a given matrix and to get the inverse of the matrix without extra cost.

## Contents

## The Faddeev-Leverrier Algorithm

Consider an n x n matrix, A. The eigenvalue of A defined as follows

can be obtained by solve the equation

where the left hand side determinant defines the characteristic polynomial of A

The Faddeev-Leverrier algorithm is an efficient approach to find the coefficients of the characteristic polynomial. In addition, the inverse matrix of A is obtained at no extra computational cost.

## MATLAB Function FADLEV

FADLEV Faddeev-Leverrier approach to generate coefficients of the characteristic polynomial and inverse of a given matrix

Uasage: [p,Ainv,B]=fedlev(A)

Input: A - the given matrix

Output: p - the coefficient vector of the characteristic polynomial

B - a cell array of the sequency of matrices generated, where

B{1} = A p(1)=trace(B{1})

B{2} = A*(B{1}-p(1)*I) p(2)=trace(B{2})/2

.....

B{n} = A*(B{n-1}-p(n-1)*I) p(n)=trace(B{n})/n

Ainv - The inverse of A calculated as

Ainv = (B{n-1}-p(n-1)*I)/p(n)

## Example 1

An integer matrix of 5 x 5

A=magic(5); [p,B]=fadlev(A); fprintf('Check inverse: norm(B-inv(A))=%g\n',norm(B-inv(A))); fprintf('Check polynomial: norm(p-poly(A))=%g\n',norm(p-poly(A)));

Check inverse: norm(B-inv(A))=2.80604e-017 Check polynomial: norm(p-poly(A))=2.10923e-009

## Example 2

A random matrix of 10 x 10

G=randn(10); [q,H]=fadlev(G); fprintf('Check inverse: norm(H-inv(G))=%g\n',norm(H-inv(G))); fprintf('Check polynomial: norm(q-poly(G))=%g\n',norm(q-poly(G)));

Check inverse: norm(H-inv(G))=8.90886e-014 Check polynomial: norm(q-poly(G))=1.28342e-012

## Reference

Vera Nikolaevna Faddeeva, "Computational Methods of Linear Algebra," (Translated From The Russian By Curtis D. Benster), Dover Publications Inc. N.Y., Date Published: 1959 ISBN: 0486604241.