Concept

Steinitz exchange lemma

The Steinitz exchange lemma is a basic theorem in linear algebra used, for example, to show that any two bases for a finite-dimensional vector space have the same number of elements. The result is named after the German mathematician Ernst Steinitz. The result is often called the Steinitz–Mac Lane exchange lemma, also recognizing the generalization by Saunders Mac Lane of Steinitz's lemma to matroids. Let and be finite subsets of a vector space . If is a set of linearly independent vectors, and spans , then:

  1. ;
  2. There is a set with such that spans . Suppose and . We wish to show that , and that after rearranging the if necessary, the set spans . We proceed by induction on . For the base case, suppose is zero. In this case, the claim holds because there are no vectors , and the set spans by hypothesis. For the inductive step, assume the proposition is true for . By the inductive hypothesis we may reorder the so that spans . Since , there exist coefficients such that At least one of must be non-zero, since otherwise this equality would contradict the linear independence of ; it follows that . By reordering the if necessary, we may assume that is nonzero. Therefore, we have In other words, is in the span of . Since this span contains each of the vectors , by the inductive hypothesis it contains . The Steinitz exchange lemma is a basic result in computational mathematics, especially in linear algebra and in combinatorial algorithms.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.