Determinant after elementary row operation

Dependencies:

1. Elementary row operation
2. Determinant
3. Swapping last 2 rows of a matrix negates its determinant

Let $A$ be an $n$ by $n$ matrix. Let $B$ be a matrix obtained by an elementary row operation on $A$. Then $|B|=r|A|$, where $r$ is a non-0 scalar. Specifically,

• $⟨i⟩\leftarrow c⟨i⟩$, where $c\ne 0$: $|B|=c|A|$.
• $⟨i⟩\leftarrow ⟨i⟩+c⟨j⟩$, where $i\ne j$: $|B|=|A|$.
• $⟨i⟩\leftrightarrow ⟨j⟩$, where $i\ne j$: $|B|=-|A|$.

Proof

Part 1: $⟨i⟩\leftarrow c⟨i⟩$

It can be proved using induction that $|B|=c|A|$ for this row operation. The base case, where $A$ is a 1 by 1 matrix, is trivial to prove.

Induction hypothesis: Assume that all $n-1$ by $n-1$ matrices satisfy $|B|=c|A|$, where $B$ is a matrix obtained by an operation of the type $⟨i⟩\leftarrow c⟨i⟩$ on $A$.

• Case 1: $i=n$ $$\begin{array}{rl}& |B|\\ & =\sum _{j=1}^n(-1{)}^{n+i}B[n,i]|B[-n,-i]|\\ & =\sum _{j=1}^n(-1{)}^{n+i}cA[n,i]|A[-n,-i]|\\ \text{(distributivity)}& & =c(\sum _{j=1}^n(-1{)}^{n+i}A[n,i]|A[-n,-i]|)& =c|A|\end{array}$$

• Case 2: $i\ne n$ $$\begin{array}{rl}& |B|\\ & =\sum _{j=1}^n(-1{)}^{n+i}B[n,i]|B[-n,-i]|\\ \text{(by induction hypothesis)}& & =\sum _{j=1}^n(-1{)}^{n+i}A[n,i](c|A[-n,-i]|)\text{(distributivity)}& & =c(\sum _{j=1}^n(-1{)}^{n+i}A[n,i]|A[-n,-i]|)& =c|A|\end{array}$$

Therefore, $|B|=c|A|$ for all $n$ by induction.

Part 3: $⟨i⟩\leftrightarrow ⟨j⟩,\text{ where }i\ne j$

It is already known that $|B|=-|A|$ for $⟨n-1⟩\leftrightarrow ⟨n⟩$

It can be proved using induction that $|B|=-|A|$ for $⟨i⟩\leftrightarrow ⟨j⟩$, where $i\ne j$.

When $n=2$, $⟨n-1⟩\leftrightarrow ⟨n⟩$ is the only row operation which swaps rows, for which we have already proved that $|B|=-|A|$.

Without loss of generality, assume that $i<j$.

Induction hypothesis: For $n\ge 3$, assume that all $n-1$ by $n-1$ matrices satisfy $|B|=-|A|$, where $B$ is a matrix obtained by the operation $⟨i⟩\leftrightarrow ⟨j⟩$ on $A$.

• Case 1: $i<j<n$. $$\begin{array}{rl}& |B|\\ & =\sum _{j=1}^n(-1{)}^{n+i}B[n,i]|B[-n,-i]|\\ \text{(by induction hypothesis)}& & =\sum _{j=1}^n(-1{)}^{n+i}A[n,i](-|A[-n,-i]|)\text{(distributivity)}& & =-(\sum _{j=1}^n(-1{)}^{n+i}A[n,i]|A[-n,-i]|)& =-|A|\end{array}$$

• Case 2: $i<j=n$

  The operation $⟨i⟩\leftrightarrow ⟨n⟩$ is the composition of these 3 operations:

  • $⟨i⟩\leftrightarrow ⟨n-1⟩$
  • $⟨n-1⟩\leftrightarrow ⟨n⟩$
  • $⟨i⟩\leftrightarrow ⟨n-1⟩$

  For the above operations, we have already proved that $|B|=-|A|$. Therefore, $|B|=-(-(-|A|))=-|A|$ for $⟨i⟩\leftrightarrow ⟨n⟩$.

Therefore, $|B|=-|A|$ for all $n$ by induction.

Part 4: $⟨i⟩\leftarrow ⟨i⟩+c⟨j⟩,\text{ where }i\ne j$

It can be proved using induction that $|B|=|A|$ for this row operation.

Base case $n=2$:

Let $A=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$.

For the operation $⟨2⟩\leftarrow ⟨2⟩+k⟨1⟩$: $$|B|=\left|\begin{array}{cc}a& b\\ c+ka& d+kb\end{array}\right|=(d+kb)a-(c+ka)b=ad-bc=\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|=|A|$$

The operation $⟨1⟩\leftarrow ⟨1⟩+k⟨2⟩$ is equivalent to the composition of:

• $⟨1⟩\leftrightarrow ⟨2⟩$
• $⟨2⟩\leftarrow ⟨2⟩+k⟨1⟩$:
• $⟨1⟩\leftrightarrow ⟨2⟩$

The first and third operations both change the sign of the determinant. So the operation $⟨1⟩\leftarrow ⟨1⟩+k⟨2⟩$ has no effect on the determinant.

Inductive step:

For $n\ge 3$, for all $n-1$ by $n-1$ matrices, $|B|=|A|$ where $B$ is obtained from $A$ by the operation $⟨i⟩\leftarrow ⟨i⟩+k⟨j⟩$.

• Case 1: $i<n\wedge j<n$ $$\begin{array}{rl}& |B|\\ & =\sum _{j=1}^n(-1{)}^{n+i}B[n,i]|B[-n,-i]|\\ \text{(by induction hypothesis)}& & =\sum _{j=1}^n(-1{)}^{n+i}A[n,i]|A[-n,-i]|& =|A|\end{array}$$

• Case 2: $i=n\wedge j<n$

  $⟨n⟩\leftarrow ⟨n⟩+c⟨j⟩$ is a composition of three operations:

  • $⟨k⟩\leftrightarrow ⟨n⟩$
  • $⟨k⟩\leftarrow ⟨n-1⟩+c⟨j⟩$
  • $⟨k⟩\leftrightarrow ⟨n⟩$

  Here $k<n$ and $k\ne j$. Such a $k$ exists since $n\ge 3$. The first and third operations change the sign of the determinant, so overall the determinant remains unchanged.

• Case 3: $i<n\wedge j=n$

  $⟨i⟩\leftarrow ⟨i⟩+c⟨n⟩$ is a composition of three operations:

  • $⟨k⟩\leftrightarrow ⟨n⟩$
  • $⟨i⟩\leftarrow ⟨i⟩+c⟨k⟩$
  • $⟨k⟩\leftrightarrow ⟨n⟩$

  Here $k<n$ and $k\ne i$. Such a $k$ exists since $n\ge 3$. The first and third operations change the sign of the determinant, so overall the determinant remains unchanged.

Therefore, $|B|=|A|$ for all $n$ by induction.

Dependency for:

1. Determinant of scalar product of matrix
2. A matrix is full-rank iff its determinant is non-0

Info:

• Depth: 6
• Number of transitive dependencies: 8

Transitive dependencies:

1. Group
2. Ring
3. Semiring
4. Matrix
5. Submatrix
6. Determinant
7. Swapping last 2 rows of a matrix negates its determinant
8. Elementary row operation