[proofplan] We prove that each listed operation preserves exactly the same linearly independent subsets of columns. Since the represented matroid is defined solely by these column-independence relations, [preservation of independence](/theorems/1116) for every subset $I \subset E$ implies equality of represented matroids. The row operations are handled by injective or bijective linear maps on the ambient column space, while column scaling is handled by an invertible change of coefficients in every linear relation. [/proofplan] [step:Reduce the assertion to preservation of linear relations on every subset] Let $A$ have row set $R$, so each column is a vector $a_e \in k^R$. Let $A'$ be obtained from $A$ by one of the listed operations, and write $a'_e$ for the column of $A'$ indexed by $e$. It is enough to prove that for every finite subset $I \subset E$, the family $(a_e)_{e \in I}$ is linearly independent over $k$ if and only if the family $(a'_e)_{e \in I}$ is linearly independent over $k$. Indeed, $M[A]$ and $M[A']$ have the same ground set $E$, and their independent sets are defined exactly by these finite independence conditions. Once the equivalence is proved for one operation, the result for a finite sequence follows by induction on the number of operations. [/step] [step:Apply an invertible row operation as a vector-space automorphism] Suppose $A'$ is obtained from $A$ by an invertible row operation. Such an elementary invertible row operation is represented by an invertible $k$-[linear map](/page/Linear%20Map) on the row-coordinate [vector space](/page/Vector%20Space), so there is a $k$-linear automorphism $T:k^R \to k^R$ such that $a'_e = T(a_e)$ for every $e \in E$. Let $I \subset E$ be finite and let $(c_e)_{e \in I}$ be a family of scalars in $k$. By linearity of $T$, \begin{align*} \sum_{e \in I} c_e a'_e = T\left(\sum_{e \in I} c_e a_e\right). \end{align*} Because $T$ is injective, \begin{align*} \sum_{e \in I} c_e a'_e = 0 \iff \sum_{e \in I} c_e a_e = 0. \end{align*} Thus every zero linear relation among $(a'_e)_{e \in I}$ has all coefficients $c_e = 0$ if and only if every zero linear relation among $(a_e)_{e \in I}$ has all coefficients $c_e = 0$. Therefore invertible row operations preserve the represented matroid. [/step] [step:Delete a zero row by restricting an isomorphism from the column span] Suppose $r_0 \in R$ is a zero row of $A$, and let $A'$ be obtained by deleting this row. Then the row set of $A'$ is $R' = R \setminus \{r_0\}$, and each column $a_e \in k^R$ has $r_0$-coordinate equal to $0$. Define the coordinate-deletion map $\pi:k^R \to k^{R'}$ by sending a vector to its restriction to $R'$. Let \begin{align*} H = \{x \in k^R : x_{r_0} = 0\}. \end{align*} Since every column $a_e$ lies in $H$, and since $\pi|_H:H \to k^{R'}$ is a $k$-linear isomorphism, we have $a'_e = \pi(a_e)$ for every $e \in E$. Let $I \subset E$ be finite and let $(c_e)_{e \in I}$ be a family of scalars in $k$. By linearity of $\pi$, \begin{align*} \sum_{e \in I} c_e a'_e = \pi\left(\sum_{e \in I} c_e a_e\right). \end{align*} Because each $a_e$ lies in $H$, the sum $\sum_{e \in I} c_e a_e$ lies in $H$. Since $\pi|_H$ is injective, this gives \begin{align*} \sum_{e \in I} c_e a'_e = 0 \iff \sum_{e \in I} c_e a_e = 0. \end{align*} Hence deleting a zero row preserves all column-independence relations. [/step] [step:Adjoin a dependent row as the graph of a linear functional] Suppose $A'$ is obtained from $A$ by adjoining a row that is a $k$-linear combination of the existing rows. Thus the new row set is $R' = R \cup \{s\}$ for a new index $s \notin R$, and there are scalars $(\lambda_r)_{r \in R}$ in $k$ such that the new row entry in column $e$ is \begin{align*} a'_{e,s} = \sum_{r \in R} \lambda_r a_{e,r} \end{align*} for every $e \in E$. Define the $k$-linear map $T:k^R \to k^{R'}$ as follows: for $x \in k^R$, set $T(x)_r = x_r$ for each $r \in R$, and set \begin{align*} T(x)_s = \sum_{r \in R} \lambda_r x_r. \end{align*} Then $a'_e = T(a_e)$ for every $e \in E$. The map $T$ is injective because its coordinates on $R$ recover $x$ exactly. Therefore, for every finite subset $I \subset E$ and every family of scalars $(c_e)_{e \in I}$, \begin{align*} \sum_{e \in I} c_e a'_e = 0 \iff T\left(\sum_{e \in I} c_e a_e\right) = 0 \iff \sum_{e \in I} c_e a_e = 0. \end{align*} So adjoining a row in the row span of $A$ preserves all column-independence relations. [guided] The point of this operation is that the new row contains no new information: it is determined by the old rows. We encode that observation as an injective linear map from the old column space into the new one. The new row set is $R' = R \cup \{s\}$, where $s$ is the added row. Since the new row is a linear combination of the old rows, there are scalars $(\lambda_r)_{r \in R}$ in $k$ such that, in each column $e \in E$, the added coordinate is \begin{align*} a'_{e,s} = \sum_{r \in R} \lambda_r a_{e,r}. \end{align*} Define $T:k^R \to k^{R'}$ by keeping all old coordinates and adding the prescribed linear combination as the new coordinate. Thus, for $x \in k^R$, set $T(x)_r = x_r$ for each $r \in R$, and set \begin{align*} T(x)_s = \sum_{r \in R} \lambda_r x_r. \end{align*} This map is $k$-linear because each coordinate of $T(x)$ is a $k$-linear expression in the coordinates of $x$. It is also injective: if $T(x)=0$, then all old coordinates satisfy $x_r = T(x)_r = 0$ for $r \in R$, so $x=0$. For every column $e \in E$, the definition of $T$ gives $T(a_e)=a'_e$. Hence a linear relation among the new columns is exactly the image under $T$ of the corresponding linear relation among the old columns: \begin{align*} \sum_{e \in I} c_e a'_e = \sum_{e \in I} c_e T(a_e) = T\left(\sum_{e \in I} c_e a_e\right). \end{align*} Since $T$ is injective, this sum is zero if and only if the old sum is zero: \begin{align*} \sum_{e \in I} c_e a'_e = 0 \iff \sum_{e \in I} c_e a_e = 0. \end{align*} Thus the set of coefficient families giving linear relations is unchanged. Therefore a subset of columns is independent after adjoining the dependent row if and only if it was independent before adjoining the row. [/guided] [/step] [step:Rescale columns by non-zero scalars without changing the zero relations] Suppose $A'$ is obtained from $A$ by multiplying columns by non-zero scalars. Thus for each $e \in E$ there is a scalar $\mu_e \in k^\times$ such that \begin{align*} a'_e = \mu_e a_e. \end{align*} Let $I \subset E$ be finite. For a family of scalars $(c_e)_{e \in I}$ in $k$, \begin{align*} \sum_{e \in I} c_e a'_e = \sum_{e \in I} c_e \mu_e a_e. \end{align*} The assignment $(c_e)_{e \in I} \mapsto (c_e\mu_e)_{e \in I}$ is a bijection from $k^I$ to $k^I$, because each $\mu_e$ is non-zero. Therefore non-trivial coefficient families for relations among $(a'_e)_{e \in I}$ correspond exactly to non-trivial coefficient families for relations among $(a_e)_{e \in I}$. Hence $(a'_e)_{e \in I}$ is independent if and only if $(a_e)_{e \in I}$ is independent. [/step] [step:Conclude equality of the represented matroids] Each elementary operation listed in the theorem preserves the independent subsets of the column-indexing set $E$. By the reduction step, any finite sequence of such operations also preserves the independent subsets of $E$. Therefore the matroids represented before and after the operations have the same ground set and the same independent sets, so $M[A'] = M[A]$. [/step]