Wolfram Language & System Documentation Center

BunchKaufmanDecomposition

yields the Bunch–Kaufman decomposition of the Hermitian or symmetric matrix m as a triple {l,b,p}.

Details and Options

The Bunch–Kaufman decomposition is used as a Hermitian or symmetric solver, typically faster and more numerically stable than other decompositions.
The Bunch–Kaufman decomposition is also known as the LBLT decomposition. It is sometimes referred to as the LDLT decomposition, though that name more commonly refers to LDLDecomposition.
In the triple , is lower triangular with s on the diagonal, is block diagonal with and blocks, and is a permutation matrix. The symmetry of , and thus its diagonal blocks, matches the symmetry of the input matrix. »
The relationship between the original matrix and the decomposition depends on whether the original matrix is Hermitian or symmetric. For a Hermitian input matrix , they satisfy , while for a symmetric , . For a real symmetric matrix, these two equations coincide, but they differ for a complex symmetric matrix. »
BunchKaufmanDecomposition takes the follow option:
TargetStructure Automatic the structure of the returned matrices
Possible settings for TargetStructure include:

	Automatic, "Structured"	return l as a LowerTriangularMatrix object, b as a BlockDiagonalMatrix object and p as a PermutationMatrix object
	"Dense"	return all matrices as lists of lists
	"Sparse"	return all matrices as SparseArray objects

BunchKaufmanDecomposition extends LDLDecomposition to all Hermitian matrices as well as complex symmetric matrices, at the cost of introducing blocks in the diagonal matrix and adding the permutation matrix ("pivoting"). »
The LDL decomposition of a Hermitian matrix is guaranteed to exist if is positive definite or negative definite, but not when is indefinite. When the permutation matrix returned by the Bunch–Kaufman decomposition is the identity matrix and there are no blocks, the LDL decomposition also exists and is identical to the Bunch–Kaufman decomposition. However, it is possible for the LDL decomposition to exist and be different from the Bunch–Kaufman decomposition. »
For a Hermitian positive definite input, the Bunch–Kaufman decomposition often coincides with the LDL decomposition. Since the LDL decomposition can be used to construct the Cholesky decomposition as , BunchKaufmanDecomposition can be considered an extension of CholeskyDecomposition to all Hermitian matrices. »

Examples

open all close all

Basic Examples (2)

Compute the Bunch–Kaufman decomposition of a real symmetric matrix:

Wolfram Language code:

m = (⁠|   |   |   |
| - | - | - |
| 2 | 5 | 4 |
| 5 | 2 | 6 |
| 4 | 6 | 8 |⁠);
{l, b, p} = BunchKaufmanDecomposition[m]

Format the result:

Wolfram Language code: MatrixForm /@ %

Confirm the decomposition:

Wolfram Language code: p.m.p == l.b.l

Compute the Bunch–Kaufman decomposition of a complex Hermitian matrix:

Wolfram Language code:

m = (⁠|              |              |              |              |
| ------------ | ------------ | ------------ | ------------ |
| -3.4         | 3.1  + 3.1 I | -2.6 + 2. I  | 6.  + 3.6 I  |
| 3.1  - 3.1 I | -6.3         | -3.1 + 4.5 I | 1.2  + 9.5 I |
| -2.6 - 2. I  | -3.1 - 4.5 I | 6.7          | -7.6 - 3.9 I |
| 6.  - 3.6 I  | 1.2  - 9.5 I | -7.6 + 3.9 I | -8.3         |⁠);
{l, b, p} = BunchKaufmanDecomposition[m]

Format the result; notice that the diagonal block in b is itself Hermitian:

Wolfram Language code: MatrixForm /@ Chop[%]

Verify the decomposition:

Wolfram Language code: p.m.Transpose[p] - l.b.ConjugateTranspose[l]//Chop

Scope (7)

Basic Uses (7)

The Bunch–Kaufman decomposition of a real symmetric machine-precision matrix:

Wolfram Language code: BunchKaufmanDecomposition[Symmetrize[RandomReal[{-10, 10}, {6, 6}], Symmetric[{1, 2}]]]

The triangular and block diagonal matrices are machine precision, but the permutation matrix is exact:

Wolfram Language code: MatrixForm /@ %

The Bunch–Kaufman decomposition of a complex Hermitian machine-precision matrix:

Wolfram Language code:

SeedRandom[RandomGeneratorState[{"ExtendedCA", {80, 4, 0}}, 
 {{RawArray["UnsignedInteger64", {16407178953997097818, 7368930915502246791, 5756465, 
     6293977506877026824, 12672308152834613335, 13417613018795460498, 17080942302500744723, 
     5459500870563 ... 44002455289743, 10936982829512251664, 14835928000192034811, 
     13752836467989677721, 1054251394126103111, 17310067405974001226, 14978545882044570653, 
     8934845044304615339}], 4, 0}}, RawArray["UnsignedInteger64", {12505010300297324358, 0}]]];
h = Symmetrize[RandomComplex[{-10 - 10 * I, 10 + 10 * I}, {6, 6}], Hermitian[{1, 2}]];

Wolfram Language code: {l, b, p} = BunchKaufmanDecomposition[h]

The and blocks in are Hermitian; in particular, elements on 's main diagonal are real:

Wolfram Language code: MatrixForm /@ b["Blocks"]//Chop

Up to numerical error, :

Wolfram Language code: MinMax[Chop[p.Normal[h].Transpose[p] - l.b.ConjugateTranspose[l]]]

The Bunch–Kaufman decomposition of a complex symmetric machine-precision matrix:

Wolfram Language code:

s = Symmetrize[RandomComplex[{-10 - 10 * I, 10 + 10 * I}, {20, 20}], Symmetric[{1, 2}]];
{l, b, p} = BunchKaufmanDecomposition[s]

The and blocks in are symmetric; in particular, there can be complex elements on 's diagonal:

Wolfram Language code: MatrixForm /@ b["Blocks"]

Up to numerical error, :

Wolfram Language code: MinMax[Chop[p.s.Transpose[p] - l.b.Transpose[l]]]

Use BunchKaufmanDecomposition with an exact matrix:

Wolfram Language code:

MatrixForm /@ BunchKaufmanDecomposition[(|             |             |       |
| ----------- | ----------- | ----- |
| 1           | 2 + Sqrt[2] | 3 + π |
| 2 + Sqrt[2] | E           | I     |
| 3 + π       | -I          | 0     |)]

Bunch–Kaufman decomposition for matrices of arbitrary-precision numbers:

Wolfram Language code: MatrixForm /@ BunchKaufmanDecomposition[RandomVariate[GaussianOrthogonalMatrixDistribution[3], WorkingPrecision -> 30]]

The precision of the lower triangular and block diagonal matrices generally maintains the precision of the input:

Wolfram Language code: Precision[%]

Bunch–Kaufman decomposition for a symbolic matrix:

Wolfram Language code:

MatrixForm /@ BunchKaufmanDecomposition[(|              |   |
| ------------ | - |
| 1            | a |
| Conjugate[a] | 5 |)]

The Bunch-Kaufman decomposition for a large numerical matrix is computed efficiently:

Wolfram Language code:

m = RandomVariate[GaussianOrthogonalMatrixDistribution[1000]];
AbsoluteTiming[BunchKaufmanDecomposition[m];]

Note that m has a million entries:

Wolfram Language code: Dimensions[m]

Options (2)

TargetStructure (2)

By default, structure matrices are returned:

Wolfram Language code:

mat = Symmetrize[RandomComplex[{-1 - I, 1 + I}, {4, 4}], Hermitian[{1, 2}]];
{l, b, p} = BunchKaufmanDecomposition[mat]

This is the same as the setting TargetStructure  "Structured":

Wolfram Language code: % === BunchKaufmanDecomposition[mat, TargetStructure -> "Structured"]

Set it to return dense results:

Wolfram Language code: {l2, b2, p2} = BunchKaufmanDecomposition[mat, TargetStructure -> "Dense"]

Though these are different objects, they represent the same result and are equal to the original output:

Wolfram Language code: {l2 == l, b2 == b, p2 == p}

Request the results as sparse arrays:

Wolfram Language code: BunchKaufmanDecomposition[Symmetrize[RandomReal[{-10, 10}, {6, 6}], Symmetric[{1, 2}]], TargetStructure -> "Sparse"]

Properties & Relations (6)

For a complex Hermitian matrix, the input matrix obeys :

Wolfram Language code:

h = Symmetrize[RandomComplex[1 + I, {3, 3}], Hermitian[{1, 2}]];
{lh, bh, ph} = BunchKaufmanDecomposition[h];
ph.h.ph == lh.bh.lh

For a complex symmetric matrix, the input matrix satisfies :

Wolfram Language code:

s = Symmetrize[RandomComplex[1 + I, {3, 3}], Symmetric[{1, 2}]];
{ls, bs, ps} = BunchKaufmanDecomposition[s];
ps.s.ps == ls.bs.ls

These formulas are not equivalent:

Wolfram Language code: {ph.h.ph == lh.bh.lh, ps.s.ps == ls.bs.ls}

However, since real symmetric and real Hermitian matrices coincide, both formulas can be used for real input:

Wolfram Language code:

r = Symmetrize[RandomReal[1, {3, 3}], Symmetric[{1, 2}]];
{lr, br, pr} = BunchKaufmanDecomposition[r];
HermitianMatrixQ[r] && pr.r.pr == lr.br.lr && pr.r.pr == lr.br.lr

Since permutation matrices are real orthogonal, the input matrix can be recovered as in the Hermitian case:

Wolfram Language code:

h = Symmetrize[RandomComplex[1 + I, {3, 3}], Hermitian[{1, 2}]];
{lh, bh, ph} = BunchKaufmanDecomposition[h];
h == ph.lh.bh.lh.ph

And as the symmetric case:

Wolfram Language code:

s = Symmetrize[RandomComplex[1 + I, {3, 3}], Symmetric[{1, 2}]];
{ls, bs, ps} = BunchKaufmanDecomposition[s];
s == ps.ls.bs.ls.ps

The symmetry of the block-diagonal matrix in the decomposition matches the symmetry of the input matrix:

Wolfram Language code:

h = Symmetrize[RandomComplex[1 + I, {20, 20}], Hermitian[{1, 2}]];
{lh, bh, ph} = BunchKaufmanDecomposition[h];
TensorSymmetry[bh]

Wolfram Language code:

h = Symmetrize[RandomComplex[1 + I, {20, 20}], Symmetric[{1, 2}]];
{lh, bh, ph} = BunchKaufmanDecomposition[h];
TensorSymmetry[bh]

BunchKaufmanDecomposition will work on any Hermitian matrix:

Wolfram Language code:

m = (⁠|   |   |   |
| - | - | - |
| 0 | 2 | 1 |
| 2 | 2 | 3 |
| 1 | 3 | 4 |⁠);
HermitianMatrixQ[m]

Wolfram Language code: BunchKaufmanDecomposition[mat]

LDLDecomposition fails for some Hermitian matrices, such as this one, when pivoting is required:

Wolfram Language code: LDLDecomposition[m]

Such matrices are neither positive nor negative definite:

Wolfram Language code: PositiveDefiniteMatrixQ[m] || NegativeDefiniteMatrixQ[m]

For the following matrix, BunchKaufmanDecomposition does not use pivoting and the block diagonal matrix has no blocks:

Wolfram Language code:

noPivotDiagonal = SymmetrizedArray[StructuredArray`StructuredData[{4, 4}, 
  {{{1, 1} -> 0.9522358578605561, {1, 2} -> 0.6623050421076754, {1, 3} -> 0.17625258657137377, 
    {1, 4} -> 0.4947848612877843, {2, 2} -> 0.28112053171866624, {2, 3} -> 0.14335614166718358, 
    {2, 4} -> 0.39283020246124734, {3, 3} -> 0.6313091437316813, {3, 4} -> 0.5768535073588343, 
    {4, 4} -> 0.9640275388436799}, Hermitian[{1, 2}]}]];
{l, b, p} = BunchKaufmanDecomposition[noPivotDiagonal];
{p == IdentityMatrix[Length[noPivotDiagonal]], DiagonalMatrixQ[b]}

As a result, the Bunch–Kaufman decomposition coincides with the LDL decomposition:

Wolfram Language code:

{ℓ, d} = LDLDecomposition[noPivotDiagonal];
l == ℓ && d == b

For the following matrix, BunchKaufmanDecomposition does not use pivoting, but there are blocks:

Wolfram Language code:

noPivotBlocks = SymmetrizedArray[StructuredArray`StructuredData[{4, 4}, 
  {{{1, 1} -> 0.31409114975717345, {1, 2} -> 0.9296201158260893, {1, 3} -> 0.4380740997319761, 
    {1, 4} -> 0.3863400364059515, {2, 2} -> 0.4120399083786235, {2, 3} -> 0.7411387665471949, 
    {2, 4} -> 0.46915083394191914, {3, 3} -> 0.38601806205067835, {3, 4} -> 0.7551830977005005, 
    {4, 4} -> 0.23956653728429456}, Hermitian[{1, 2}]}]];
{l, b, p} = BunchKaufmanDecomposition[noPivotBlocks];
{p == IdentityMatrix[Length[noPivotBlocks]], DiagonalMatrixQ[b]}

Consequently, the Bunch–Kaufman decomposition differs from the LDL decomposition:

Wolfram Language code:

{ℓ, d} = LDLDecomposition[noPivotBlocks];
l == ℓ || d == b

Finally, for this matrix, BunchKaufmanDecomposition uses pivoting:

Wolfram Language code:

pivotDiagonal = SymmetrizedArray[StructuredArray`StructuredData[{4, 4}, 
  {{{1, 1} -> 0.47619054005221373, {1, 2} -> 0.41489787499498676, {1, 3} -> 0.826113894123858, 
    {1, 4} -> 0.2787158070316167, {2, 2} -> 0.7485827836683288, {2, 3} -> 0.20876586927526475, 
    {2, 4} -> 0.37069120649409415, {3, 3} -> 0.5480360624388212, {3, 4} -> 0.5333605049010796, 
    {4, 4} -> 0.19683262635198728}, Hermitian[{1, 2}]}]];
{l, b, p} = BunchKaufmanDecomposition[pivotDiagonal];
{p == IdentityMatrix[Length[pivotDiagonal]], DiagonalMatrixQ[b]}

Even though the matrix is diagonal, it cannot be the same as the matrix returned by LDLDecomposition:

Wolfram Language code:

{ℓ, d} = LDLDecomposition[pivotDiagonal];
l == ℓ || d == b

For a randomly generated positive definite Hermitian, there is roughly a probability that the LDL and Bunch–Kaufman decompositions coincide:

Wolfram Language code:

mList = #.#& /@ RandomComplex[1 + I, {1000, 4, 4}];
ldlCoincides[m_] := Module[{l, b, p}, {l, b, p} = BunchKaufmanDecomposition[m];DiagonalMatrixQ[b] && p == IdentityMatrix[Length[m]]]
good = Select[mList, ldlCoincides];
N[Length[good] / Length[mList]]

When they do, the Cholesky decomposition can be recovered as :

Wolfram Language code:

m = First[good];
c = CholeskyDecomposition[m];
{l, b, p} = BunchKaufmanDecomposition[m];
c == Sqrt[b].l

Conversely, can be constructed by squaring the diagonal of and by normalizing with its diagonal:

Wolfram Language code: b == DiagonalMatrix[Diagonal[c]^2] && l == ConjugateTranspose[c / Diagonal[c]]

For positive definite matrices, the matrix is diagonal with probability 1:

Wolfram Language code: mList === Select[mList, DiagonalMatrixQ[BunchKaufmanDecomposition[#][[2]]]&]

Thus, when Cholesky cannot be recovered from Bunch–Kaufman, it is due to nontrivial pivoting:

Wolfram Language code: Last[BunchKaufmanDecomposition[First[Complement[mList, good]]]]

Top

More Learning

Tech Support

Wolfram Solutions

Wolfram Solutions For Education

Get Started

Grow Your Skills

Work with Us

Educational Programs for Adults

Educational Programs for Youth

Read

BunchKaufmanDecomposition

Details and Options

Examples

Basic Examples (2)

Scope (7)

Basic Uses (7)

Options (2)

TargetStructure (2)

Properties & Relations (6)

Text

CMS

APA

BibTeX

BibLaTeX

BunchKaufmanDecomposition

Details and Options

Examples

Basic Examples (2)

Scope (7)

Basic Uses (7)

Options (2)

TargetStructure (2)

Properties & Relations (6)

See Also

Related Guides

History

Text

CMS

APA

BibTeX

BibLaTeX