Gaussian Elimination Elements $a^{(r)}_{ij}$

45 Views Asked by At

Let $A\in \mathbb{R}^{n\times n}$. We apply GE to it. Prove that:

$\begin{align} a^{(r)}_{ij}&= a^{(r)}_{ij}=\frac{A\begin{pmatrix} 1 & 2 &\cdots & r & i \\ 1 & 2 &\cdots & r & j \end{pmatrix}}{A\begin{pmatrix} 1 & 2 &\cdots & r \end{pmatrix}} \end{align}$

where $A\begin{pmatrix} 1 & 2 &\cdots & r \end{pmatrix}=A\begin{pmatrix} 1 & 2 &\cdots & r \\ 1 & 2 &\cdots & r \end{pmatrix}$ and $A\begin{pmatrix} 1 & 2 &\cdots & r & i \\ 1 & 2 &\cdots & r & j \end{pmatrix}=det\begin{pmatrix} a_{11} & a_{12} &... & a_{1j} \\ . & & &. \\ . & & & .\\ . & & &.\\ a_{i1} & a_{i2} &... &a_{ij} \end{pmatrix} $

My work so far: I have shown that the hypothesis is true for $r=1$ using the formula $$a^{(1)}_{ij}=a_{ij}-\frac{a_{i1}}{a_{11}}a_{1j}$$ I try to prove the rest using induction. Suppose there is a $r=p$ such that

\begin{align} a^{(p)}_{ij}=\frac{A\begin{pmatrix} 1 & 2 &\cdots & p & i \\ 1 & 2 &\cdots & p & j \end{pmatrix}}{A\begin{pmatrix} 1 & 2 &\cdots & p \end{pmatrix}} \end{align} Then for $r=p+1$, using $a_{ij}^{(p+1)} = a^{(p)}_{ij}-\frac{a^{(p)}_{ip+1}}{a^{(p)}_{p+1p+1}}a^{(p)}_{p+1j}$ I concluded to:

\begin{align} a^{(p+1)}&= \frac{A\begin{pmatrix} 1 & \cdots & p & i\\ 1 & \cdots & p & j \end{pmatrix}}{A\begin{pmatrix} 1 &\cdots &p \\ 1 &\cdots &p \end{pmatrix}} -\frac{A\begin{pmatrix} 1 & \cdots & p & i \\ 1 & \cdots & p & p+1 \end{pmatrix}A\begin{pmatrix} 1 & \cdots &p &p+1 \\ 1 &\cdots &p &j \end{pmatrix}}{A\begin{pmatrix} 1 &\cdots &p \\ 1 &\cdots &p \end{pmatrix}A\begin{pmatrix} 1 &\cdots &p & p+1 \\ 1 & \cdots &p &p+1 \end{pmatrix}} \end{align} How can I proceed?

1

There are 1 best solutions below

0
On

Elaborating on my comment: assuming that $A(1\cdots k)\ne0$ for all $1\le k\le p$ for some $p\le n-1$, after the $p$-th reduction step the partially reduced matrix looks like $$G_p=\begin{pmatrix} a_{11}&a_{12}&\cdots&a_{1p}&a_{1,p+1}&\cdots&a_{1n}\\ &a^{(1)}_{22}&\cdots&a^{(1)}_{2p}&a^{(1)}_{2,p+1}&\cdots&a^{(1)}_{2n}\\ &&\ddots&\vdots&\vdots&\ddots&\vdots\\ &&&a^{(p-1)}_{pp}&a^{(p-1)}_{p,p+1}&\cdots&a^{(p-1)}_{pn}\\ &&&&a^{(p)}_{p+1,p+1}&\cdots&a^{(p)}_{p+1,n}\\ &&&&\vdots&\ddots&\vdots\\ &&&&a^{(p)}_{n,p+1}&\cdots&a^{(p)}_{nn} \end{pmatrix}$$ Therefore since minors from $A$ and $G_p$ among the first rows are equal, $$A(1\cdots p)=\begin{vmatrix} a_{11}&a_{12}&\cdots&a_{1p}\\ &a^{(1)}_{22}&\cdots&a^{(1)}_{2p}\\ &&\ddots&\vdots\\ &&&a^{(p-1)}_{pp}\\ \end{vmatrix}=a_{11}a^{(1)}_{22}\cdots a^{(p-1)}_{pp}\ne0$$ and for $p+1\le i,j\le n$, $$A\begin{pmatrix} 1&\cdots&p&i\\ 1&\cdots&p&j \end{pmatrix}=\begin{vmatrix} a_{11}&a_{12}&\cdots&a_{1p}&a_{1j}\\ &a^{(1)}_{22}&\cdots&a^{(1)}_{2p}&a^{(1)}_{2j}\\ &&\ddots&\vdots&\vdots\\ &&&a^{(p-1)}_{pp}&a^{(p-1)}_{pj}\\ &&&&a^{(p)}_{ij} \end{vmatrix}=a_{11}a^{(1)}_{22}\cdots a^{(p-1)}_{pp}a^{(p)}_{ij}=A(1\cdots p)\,a^{(p)}_{ij}$$ so $$a^{(p)}_{ij}=\frac{A\begin{pmatrix} 1&\cdots&p&i\\ 1&\cdots&p&j \end{pmatrix}}{A(1\cdots p)}$$