2d:null 2e:["$","title",null,{"children":"Reduction of Integer Matrices | Sushovan Majhi | Observable"}] 33:T40f,bibtex = [ `@book{artin, title={Algebra}, author={Artin, M.}, isbn={9780132413770}, lccn={2010017573}, year={2011}, publisher={Pearson Prentice Hall} }`, `@misc{wiki_snf, author = "{Wikipedia contributors}", title = "Smith normal form --- {Wikipedia}{,} The Free Encyclopedia", year = "2021", url = "https://en.wikipedia.org/w/index.php?title=Smith_normal_form&oldid=1013684381", note = "[Online; accessed 21-July-2021]" }`, `@book{Munkres84, added-at = {2017-06-29T07:13:07.000+0200}, author = {Munkres, James R.}, howpublished = {Hardcover}, interhash = {10ba8f346353018af3b6905ac8a49e37}, intrahash = {a393fd24fb74ad14a3a577dd049bd850}, isbn = {0201045869}, keywords = {57-01-manifolds-cell-complexes-instructional-exposition 55-01-algebraic-topology-instructional-exposition}, posted-at = {2015-03-03 06:47:23}, priority = {2}, publisher = {Addison Wesley Publishing Company}, timestamp = {2019-03-25T05:31:34.000+0100}, title = {{Elements of Algebraic Topology}}, year = 1984 }` ]34:[] 31:{"id":"62c3243fbb3ea004","slug":"normal-form","title":"Reduction of Integer Matrices","thumbnail":"55dca141b74717202dc41e4c3a62e4b1ec92ccddc69494700c5ad8e99f7b3265","access_level":"public","create_time":"$D2021-07-19T21:33:07.240Z","update_time":"$D2021-10-01T18:20:25.250Z","view_time":null,"first_public_time":"$D2021-07-25T20:55:47.813Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"5c56cbc4fa1a79cc","login":"sushovan4","name":"Sushovan Majhi","avatar_url":"https://avatars-next.observableusercontent.com/b1f7f6348b412ded4f50179aa3abe09807cb91bd40ca48baba147cea364cfc21","tier":"starter_2024"},"version":2143,"publish_version":2143,"role":null,"authored":false,"authors":[{"type":"individual","id":"fe0f8e54731116c8","login":"sushovan4","name":"Sushovan Majhi","avatar_url":"https://avatars-next.observableusercontent.com/df63d9ad96b12dfa82102c65e9e1c838fa5fb7c83495cd751fd2e278ee6fd58e","tier":null}],"members":[{"type":"individual","id":"fe0f8e54731116c8","login":"sushovan4","name":"Sushovan Majhi","avatar_url":"https://avatars-next.observableusercontent.com/df63d9ad96b12dfa82102c65e9e1c838fa5fb7c83495cd751fd2e278ee6fd58e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"c42c4793e1915583","slug":"smith-normal-form","title":"Smith Normal Form","owner":{"id":"5c56cbc4fa1a79cc","login":"sushovan4","name":"Sushovan Majhi"}},"type":"notebook","body":{"title":"Reduction of Integer Matrices","cells":[{"id":0,"value":"# Reduction of Integer Matrices\n## Interactive tutorial on Smith Normal Form","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"In case you are in a haste or trying to avoid the painful math behind it, see the [*reduction in action*](https://observablehq.com/@sushovan4/normal-form-algorithm)!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":478,"value":"## 1. Introduction","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"Matrix reduction plays a fundamental role in the study of vector spaces and linear transformations. Reduction of a matrix to a *canonical* or [*normal form*](https://en.wikipedia.org/wiki/Canonical_form) finds its use in almost all applied fields of science. While there are many different normal forms a matrix can be reduced to, a normal form is usually the product of much simpler and well-understood (e.g., diagonal, upper/lower triangular, etc) matrices. Since, the reduction process faithfully carries most of the *nice* properties of the original matrix, one can use a normal form to *infer* some of those properties from matrices with relatively simple structure.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"The choice of the normal form can sometimes be demanded by a particular application, or be limited by the algebraic operations one is allowed to perform on the entries of the original matrix. Today we consider, for reduction, only ${tex`\\Z`}-matrices, i.e., matrices that are allowed to have only integer entries. As a consequence, the only permitted operations on the entries of such a matrix are *addition* and *multiplication*—but not *division*. We denote by ${tex`\\mathcal{M}_{n,m}(\\Z)`} the set of all integer matrices with ${tex`n`} rows and ${tex`m`} columns. In the special case of square matrices (${tex`m=n`}), we simply call it ${tex`\\mathcal{M}_{m}(\\Z)`} or ${tex`\\mathcal{M}_{n}(\\Z)`}. Note that the identity matrix, ${tex`I_{m}`}, of dimension ${tex`m`} is a ${tex`\\Z`}-matrix, i.e., ${tex`I_m\\in\\mathcal{M}_{m}(\\Z)`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":186,"value":"### 1.1 Permitted Matrix Operations","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1830,"value":"Although our hands are now tied by the restriction on the operations allowed on a matrix ${tex`A\\in\\mathcal{M}_{n,m}(\\Z)`}, we can still follow the usual definitions of matrix **addition**, **subtraction**, and **multiplication**— also **determinant** and **inverse** of a square matrix. For a square matrix ${tex`A\\in\\mathcal{M}_{n}(\\Z)`}, its determinant is defined the [usual way](https://en.wikipedia.org/wiki/Leibniz_formula_for_determinants). Also, ${tex`A`} is said to have an inverse ${tex`B\\in\\mathcal{M}_{n}(\\Z)`} if ${tex`AB=BA=I_n`}. The set of all invertible (square) matrices of dimension ${tex`n`} is denoted by ${tex`GL_{n}(\\Z)`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1825,"value":"### 1.2 Smith Normal Form","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":280,"value":"Given an ${tex`A\\in\\mathcal{M}_{n,m}(\\Z)`}, we seek invertible matrices ${tex`P\\in GL_{m}(\\Z)`} and ${tex`Q\\in GL_{n}(\\Z)`} such that\n${tex`D=Q^{-1}AP,`}\nwhere ${tex`D`} is an ${tex`n\\times m`} diagonal integer matrix:\n${tex.block`\n\\newcommand\\bigzero{\\makebox(0,0){\\text{\\huge0}}}\n\\begin{pmatrix}\n\\begin{array}{c:c}\n \\begin{matrix}\n d_1 & 0 & \\ldots & 0 \\\\\n 0 & d_2 & \\ldots & 0\\\\\n 0 & \\ldots & \\ldots & 0 \\\\\n 0 & \\ldots & 0 & d_k \\\\\n \\end{matrix}\n & {\\huge0}_{k,m-k} \\\\\n \\hdashline \\\\\n {\\huge0}_{n-k,k} & {\\huge0}_{n-k,m-k}\n\\end{array}\n\\end{pmatrix}\n`}\nwith ${tex`d_i\\geq0`} for all ${tex`i=1, 2, \\ldots, k`} and ${tex`d_1| d_2| \\ldots | d_k`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":393,"value":"**Note:**\n - the diagonal matrix ${tex`D`} always exists, as we allow it to be a zero matrix; it is also *unique*. \n - ${tex`P,Q`} may not, however, be unique ${citations.get('artin')}.\n - if ${tex`A`} is viewed as the matrix of a linear transformation ${tex`T:G_1\\to G_2`} between two [finitely-generated free abelian groups](https://observablehq.com/@sushovan4/basechange), then ${tex`P`} and ${tex`Q`} are the *basechange matrices* for ${tex`G_1`} and ${tex`G_2`}, respectively.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":471,"value":"### 1.3 Application","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":506,"value":"Unlike the other popular canonical forms—e.g., the Jordan normal form for matrices over an *algebraically-closed* field—the Smith normal form is particularly relevant in the context of ${tex`\\Z`}-modules, more generally ${tex`R`}-modules ${citations.get('artin')}. In the field of combinatorial topology, the reduction to Smith normal form facilitates the computation of the [homology groups](https://en.wikipedia.org/wiki/Homology_(mathematics)) of finte [simplicial complexes](https://en.wikipedia.org/wiki/Simplicial_complex) ${citations.get('Munkres84')}. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":523,"value":"## 2. Elementary Operations","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":530,"value":"As stated above without a proof that the reduction of an integer matrix to a Smith normal form always exists. We now present the steps one can perform to decompose a given matrix. The basis of the reduction process involves three **elementary operations**. We invoke them repeatedly on the original matrix in the right order. We are going to use three elementary *row operations* and three corresonding *column operations*. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1861,"value":"### 2.1 Elementary Matrices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":704,"value":"Each of the following row (and column) operations can also be described as pre (and post) multiplication by an **elementary matrix**. For each elementary operation, there is an associated elementary matrix, which is obtained by performing the same operation on the identity matrix of the right size.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":549,"value":"### 2.2 Row Operations","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":653,"value":"We first define and then demonstrate the elementary row operations. The outcome ${tex`A'`} of each row operation on ${tex`A`} is a *pre*-multiplication of ${tex`A`} by an elementary matrix ${tex`E`}, i.e., ${tex`A'=EA`}. The three types of row operations are as follows:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1661,"value":"- Multiply the ${tex`i`}-th row by ${tex`-1`}\n- Exchange the ${tex`i`}-th and ${tex`j`}-th row\n- Replace the ${tex`i`}-th row with the row plus ${tex`q`} times the ${tex`j`}-th row (${tex`i\\neq j, q\\neq 0`}) ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":645,"value":"### 2.2 Column Operations","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":851,"value":"The outcome ${tex`A'`} of each column operation on ${tex`A`} is *post*-multiplication of ${tex`A`} by an elementary matrix ${tex`E`}, i.e., ${tex`A'=AE`}. The three types of column operations are as follows:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":858,"value":"- Multiply the ${tex`i`}-th column by ${tex`-1`}\n- Exchange the ${tex`i`}-th and ${tex`j`}-th column\n- Replace ${tex`i`}-th column with the column plus ${tex`q`} times the ${tex`j`}-th column (${tex`i\\neq j, q\\neq 0`})","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":799,"value":"### 2.4 Demo ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1495,"value":"The operations are best understood when demonstrated on an example matrix. To that end, we first generate a random matrix ${tex`A`} with integer (between -5 and 5) entries by choosing the number of rows and columns using the sliders. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"viewof m = Inputs.range([1, 6], {\n value: 5,\n step: 1,\n label: md`Number of rows (${tex`n`}):`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":623,"value":"viewof n = Inputs.range([1, 6], {\n value: 4,\n step: 1,\n label: md`Number of cols (${tex`m`}):`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1886,"value":"If you do not like the random matrix, try fiddling with the above sliders to generate a new one!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":613,"value":"$${tex.block`A=${nj.mat2Tex(A)}`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1657,"value":"**See for yourself:**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1527,"value":"From the dropdown below choose the operation type (row/column) and an operation. Also, set the values of the arguemts for the operations chosen, using the sliders. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1200,"value":"viewof opType = Inputs.select([\"row\", \"col\"], {\n label: \"Type of operation\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1175,"value":"viewof operation = Inputs.select(\n Operations[opType].map((o) => o.name),\n {\n label: \"operation\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1206,"value":"viewof i = Inputs.range([1, opType === \"row\" ? n : m], {\n value: 1,\n step: 1,\n label: tex`i`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1215,"value":"viewof j = Inputs.range([1, opType === \"row\" ? n : m], {\n value: 2,\n step: 1,\n label: tex`j`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1219,"value":"viewof q = Inputs.range([-20, 20], {\n value: 10,\n step: 1,\n label: tex`q`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1533,"value":"Here is the outcome matrix:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1224,"value":"tex.block`A'=${nj.mat2Tex(Result[0])}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1537,"value":"The corresponding elementary matrix ${tex`E`} is such that ${opType === 'row' ? tex`A'=EA` : tex`A'=AE`}. As will be discussed later, we accumulate the ${tex`E^{-1}`} from the operations to compute the basechange matrix.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1699,"value":"$${tex.block`\nE=${nj.mat2Tex(Result[1])}\\text{, and }\nE^{-1}=${nj.mat2Tex(Result[2])}\n`}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1904,"value":"With all the background definitions and notations at our disposal to present the reduction algorithm.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":928,"value":"## 3. The Reduction Algorithm","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2136,"value":"Before we discuss the algorithm in detail, feel free to take a quick detour to see the [*reduction in action*](https://observablehq.com/@sushovan4/normal-form-algorithm)!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1911,"value":"Given an integer matrix ${tex`A`} of any size, its reduction to the Smith normal form follows three major steps:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1549,"value":"### Step 0: Set the offset","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":996,"value":"The algorithm relies on an `offset` parameter. Starting with `offset`=${tex`1`}, the reduction process works on the original matrix, inductively, by incrementing the offset. The offset determines how much of the matrix has been already been processed; it ranges from ${tex`1`} to ${tex`\\min\\{n,m\\}`}. When the function `reduce(offset)` is called, it assumes that the **offset-block**, block with the diagonal element `(offset,offset)` at its top-left corner, has to be processed, and all other rows and columns are already in good shape. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1945,"value":"To get an idea of how `offset` plays its role, try choosing an `offset` from the slider. If the reduction algorithm is called it would assume that the green elements are already processed, and the (gray) offset-block is yet to be processed. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1169,"value":"viewof offset = Inputs.range([1, Math.min(n, m)], {\n value: 1,\n step: 1,\n label: `offset`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1012,"value":"{\n const container = d3.create(\"div\").attr(\"class\", \"mat-container\");\n\n container\n .selectAll(\".row\")\n .data(A)\n .join(\"div\")\n .attr(\"class\", \"row\")\n .selectAll(\"div\")\n .data((d) => d)\n .join(\"div\")\n .attr(\"class\", \"element\")\n .text((d) => d);\n\n container\n .selectAll(\".row\")\n .filter((d, k) => k < offset - 1)\n .selectAll(\".element\")\n .style(\"background\", \"#BDF3C2\");\n container\n .selectAll(\".row\")\n .selectAll(\".element\")\n .filter((d, k) => k < offset - 1)\n .style(\"background\", \"#BDF3C2\");\n yield container.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1962,"value":"**A Word of Caution:** Note, however, that the green rows and columns may not be yet processed in the following demo matrix.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1555,"value":"### Step 1: Find the Best Pivot","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1973,"value":"For a given `offset`, we find the best pivot: a (non-zero) element that divides all other elements of the offset-block. This step involves finding repeatedly *a* pivot, then improving it. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":994,"value":"** Step 1.1 Find a `Pivot` and `antiPivot`:** \nFor a given offset-block, a `pivot` is a *non-zero* element with the smallest absolute value; shown with a green border below. \n\nIf the pivot-block is has all zero entries, we return the step. If not, a pivot can be found in ${tex`O(mn)`}-time.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1062,"value":"{\n const container = d3.create(\"div\").attr(\"class\", \"mat-container\");\n\n container\n .selectAll(\".row\")\n .data(A)\n .join(\"div\")\n .attr(\"class\", \"row\")\n .selectAll(\"div\")\n .data((d) => d)\n .join(\"div\")\n .attr(\"class\", \"element\")\n .text((d) => d);\n\n container\n .selectAll(\".row\")\n .filter((d, k) => k < offset - 1)\n .selectAll(\".element\")\n .style(\"background\", \"#BDF3C2\");\n container\n .selectAll(\".row\")\n .selectAll(\".element\")\n .filter((d, k) => k < offset - 1)\n .style(\"background\", \"#BDF3C2\");\n\n container\n .selectAll(\".row\")\n .filter((d, k) => k === pivot[0])\n .selectAll(\".element\")\n .filter((d, k) => k === pivot[1])\n .style(\"border\", \"2px solid green\");\n\n container\n .selectAll(\".row\")\n .filter((d, k) => k === antiPivot[0])\n .selectAll(\".element\")\n .filter((d, k) => k === antiPivot[1])\n .style(\"border\", \"2px solid red\");\n yield container.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1071,"value":"We say that pivot can still be improved if, in the offset-block, there is an `antiPivot`: an element that does not divisible by the current `pivot`. In the demo, an `antiPivot` of a `pivot` is shown with a red border.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2015,"value":"If `antiPivot` does not exist, we skip Step 1.1. Otherwise, we improve the `pivot`.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1088,"value":"** Step 1.2 Improve the Pivot**","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2024,"value":"{\n if (antiPivot.length === 0)\n return md`For the offset-block, we see that the pivot is already the best. So, we skip this step.`;\n else\n return md`For the offset-block, we see that the antiPivot exists. So, we take this step.`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2041,"value":"Let ${tex`[i,j]`} and ${tex`[s,t]`} be the positions of `pivot` and `antiPivot`.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1625,"value":"**Case I (${tex`i=s`}):** ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2065,"value":"If the `pivot` and `antiPivot` are on the same row, replace the antiPivot column by ${tex`q \\times`} the pivot column, where ${tex`a_{it}= qa_{ij}+r`} with ${tex`0 (a.author[0].family > b.author[0].family ? 1 : -1));\n const authormap = [];\n for (const [i, o] of Object.entries(authorObj)) {\n authormap.push([\n o.id,\n reftype == \"indexed\" ? `\\[${+i + 1}\\]` : `(${o.author[0].family})`\n ]);\n }\n const bibcontainer = cite.get({ type: output, style: style });\n if (reftype == \"indexed\") {\n bibcontainer.querySelectorAll(\".csl-entry\").forEach((e, i) => {\n e.innerHTML = `[${i + 1}] ${e.innerHTML}`;\n });\n }\n const result = html`${bibcontainer}`;\n result.value = new Map(authormap);\n return result;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"nj = require(\"https://bundle.run/@tdajs/normal-form@2.0.0\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":610,"value":"A = {\n let rows = n; //d3.randomInt(1, 10)();\n let cols = m; //d3.randomInt(1, 10)();\n\n return d3.range(0, rows).map((row) => {\n return d3.range(0, cols).map((elm) => d3.randomInt(-5, 5)());\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1181,"value":"Operations = {\n const obj = {\n row: [\n { name: \"exchangeRows\", args: [\"i\", \"j\"] },\n { name: \"replaceRow\", args: [\"i\", \"j\", \"q\"] },\n { name: \"multiplyRow\", args: [\"i\"] }\n ],\n col: [\n { name: \"exchangeCols\", args: [\"i\", \"j\"] },\n { name: \"replaceCol\", args: [\"i\", \"j\", \"q\"] },\n { name: \"multiplyCol\", args: [\"i\"] }\n ]\n };\n return obj;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1722,"value":"Result = {\n if (operation.includes(\"exchange\"))\n return nj[operation](i - 1, j - 1, A, { copy: true });\n else if (operation.includes(\"multiply\"))\n return nj[operation](i - 1, q, A, { copy: true });\n else return nj[operation](i - 1, j - 1, q, A, { copy: true });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1589,"value":"pivot = nj.findPivot(A, offset - 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1591,"value":"antiPivot = nj.findAntiPivot(pivot, A, offset - 1)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1731,"value":"NF = new nj.NormalForm(A)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1768,"value":"B = Array.from({ length: m }).map((e, i) => \"e_\" + i)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1772,"value":"B1 = Array.from({ length: n }).map((e, i) => \"e_\" + i + \"'\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"\n","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1","titling":"auto"}} 32:"$31:body"