{
  "id": "enwiki-001374516742",
  "slug": "samuelson-berkowitz-algorithm",
  "title": "Samuelson–Berkowitz algorithm",
  "qid": "",
  "lead": "In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an n\\times n matrix whose entries may be elements of any unital commutative ring. Unlike the Faddeev–LeVerrier algorithm, it performs no divisions, so may be applied to a wider range of algebraic structures.",
  "body": "In mathematics, the Samuelson–Berkowitz algorithm efficiently computes the characteristic polynomial of an n\\times n matrix whose entries may be elements of any unital commutative ring. Unlike the Faddeev–LeVerrier algorithm, it performs no divisions, so may be applied to a wider range of algebraic structures. ==Description of the algorithm== The Samuelson–Berkowitz algorithm applied to a matrix A produces a vector whose entries are the coefficient of the characteristic polynomial of A . It computes this coefficients vector recursively as the product of a Toeplitz matrix and the coefficients vector an (n-1)\\times(n-1) principal submatrix. Let A_0 be an n\\times n matrix partitioned so that A_0 = \\left[ \\begin{array}{c|c} a_{1,1} & R \\\\ \\hline C & A_1 \\end{array} \\right] The first principal submatrix of A_0 is the (n-1)\\times(n-1) matrix A_1 . Associate with A_0 the (n+1)\\times n Toeplitz matrix T_0 defined by T_0 = \\left[ \\begin{array}{c} 1 \\\\ -a_{1,1} \\end{array} \\right] if A_0 is 1\\times 1 , T_0 = \\left[ \\begin{array}{c c} 1 & 0 \\\\ -a_{1,1} & 1 \\\\ -RC & -a_{1,1} \\end{array} \\right] if A_0 is 2\\times 2 , and in general T_0 = \\left[ \\begin{array}{c c c c c} 1 & 0 & 0 & 0 & \\cdots\\\\ -a_{1,1} & 1 & 0 & 0 & \\cdots\\\\ -RC & -a_{1,1} & 1 & 0 & \\cdots\\\\ -RA_1C & -RC & -a_{1,1} & 1 & \\cdots\\\\ -RA_1^2C & -RA_1C & -RC & -a_{1,1} & \\cdots\\\\ \\vdots & \\vdots & \\vdots & \\vdots & \\ddots \\end{array} \\right] That is, all super diagonals of T_0 consist of zeros, the main diagonal consists of ones, the first subdiagonal consists of -a_{1,1} and the k th subdiagonal consists of -RA_1^{k-2}C . The algorithm is then applied recursively to A_1 , producing the Toeplitz matrix T_1 times the characteristic polynomial of A_2 , etc. Finally, the characteristic polynomial of the 1\\times 1 matrix A_{n-1} is simply T_{n-1} . The Samuelson–Berkowitz algorithm then states that the vector v defined by v=T_0 T_1 T_2\\cdots T_{n-1} contains the coefficients of the characteristic polynomial of A_0 . Because each of the T_i may be computed independently, the algorithm is highly parallelizable. ==References==",
  "categories": [
    "22937263",
    "23060232",
    "23118434",
    "23603337",
    "26709309",
    "26709316"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1374516742",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1789219187.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001374516742",
    "type": "webpage",
    "title": "Samuelson–Berkowitz algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/samuelson-berkowitz-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          11
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          11
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001374516742",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1374516742",
    "note": "Immutable snapshot enwiki-001374516742"
  }
}