7

I am reading Tapp's Introduction to Matrix Groups for Undergraduates and he writes:

Let $V$ be an $n$-dimensional (left) vector space over $\mathbb K$. Then $V$ is isomorphic to $\mathbb K^n$. In fact, there are many isomorphisms from $V$ to $\mathbb K^n$. For any ordered basis $v_1, \dots, v_n$ of $V$ the following is an isomorphism:

$(c_1 v_1 + \dots + c_n v_n) \mapsto (c_1, \dots, c_n)$

My question is:

(1) Are all finite dimensional bases in linear algebra courses in general automatically assumed to be ordered because writing $b_1, \dots, b_n$ is an order?

(2) It seems to me that the order is irrelevant in the sense that the isomorphism above could just as well map $(c_1 v_1 + \dots + c_n v_n) \mapsto (c_n, \dots, c_1)$. Hence my question: is it possible to give an isomorphism without using an ordered basis?

Bingo
  • 1,774
learner
  • 1,967
  • Just a side remark : Ordered basis for a vector space is used when one wants to talk about orientation of the vector space. So for example when we want to talk about orientability of a manifold we need to deal with ordered basis of tangent spaces. – Bingo Dec 13 '14 at 04:35
  • @MarcvanLeeuwen I've realized from your last comment (there is a bijection between the ordered basis and the set of isomorphisms) that you are indeed correct. I've deleted my answer, and I would like the OP to focus on this statement in particular. – Gyu Eun Lee Dec 14 '14 at 02:33
  • @neuguy Thank you for your comment. I am still in the process of trying to understand. – learner Dec 14 '14 at 02:34
  • @neuguy but now I can't see your comments because they are deleted? – learner Dec 14 '14 at 02:35
  • 1
    @learner I have undeleted for the sake of the comments, but I will add an edit saying that my answer is incorrect. – Gyu Eun Lee Dec 14 '14 at 02:35
  • @neuguy Sounds good, thank you! – learner Dec 14 '14 at 02:37
  • “Ordered bases” are necessary for associating matrices to linear maps. – egreg Dec 14 '14 at 15:59

3 Answers3

11

Since a basis is almost always written down in a specific order, it is actually more difficult to talk about unordered bases than about ordered bases. You could say "let $\def\B{\mathcal B}\B\subset V$ be a basis" but there is not so much one can do with just that. As soon as you even just say "let $\B=\{b_1,\ldots,b_n\}$" to mention its vectors, you are in fact specifying (choosing) an ordering on those vectors, and therefore introducing an ordered basis. If you really want to work with unordered basis, you might say: let $I$ be an (unspecified index) set of size $n$, and let $\B=\{\,b_i\mid i\in I\,\}$, but best would be to not use index notation at all.

Since the components of elements of $K^n$ come in a specific order (in the isomorphism defined in the question, the components $c_i$ form a $n$-tuple in the result, not a set), defining an isomorphism $V\to K^n$ requires using an ordered basis; using an unordered basis the isomorphism cannot be uniquely defined. Of course one can pick any ordering of the basis, but that gives $n!$ different choices for an isomorphism where one needs to have a single one. That is why you book talks about an ordered basis in this context.

So to answer your questions. (1) Yes I am convinced that in most linear algebra courses, bases one works with are always assumed to be ordered bases. You might have some occasions where you consider a basis just as a set of vectors, but as soon as it comes down to expressing vectors in coordinates and writing down matrices (and I think most linear algebra courses do that a lot, especially the introductory ones), bases need to be ordered. (2) While every ordering of an unordered basis gives an equally good isomorphism with $K^n$, one does need to select an ordering in order to get ones hands on a specific isomorphism.

Maybe in some sense you could define an isomorphism using only an unordered basis, or indeed without using any basis at all, but it would always be cheating by depending on some other choice. For instance you could say, since $\dim V=n$ the set of isomorphisms $V\to K^n$ is non-empty; so pick one of them. But however you got hold of a specific isomorphism, that isomorphism picks out one specific ordered basis of $V$, namely the ordered set of vectors which, in order, map to the successive elements $e_1,\ldots,e_n$ of the standard basis of$~K^n$. Choosing an isomorphism is exactly choosing an ordered basis.

To make this into a precise statement: there is a natural bijection between the set of ordered bases of $V$ and the set of isomorphisms $V\to K^n$, which associates to an ordered basis $[b_1,\ldots,b_n]$ the isomorphism $(c_1b_1+\cdots+c_nb_n)\mapsto(c_1,\ldots,c_n)$ (the linear map associating to $v\in V$ its $n$-tuples of coordinates with respect to the chosen ordered basis). No such natural bijection exists for the set of unordered bases of$~V$ (which can be seen as a quotient of the set of ordered bases, under the $n!$ permutations of the elements of each basis).

  • I have a question regarding your answer to (2): say, I pick two unspecified orderings $\B={,b_i\mid i\in I,}$ of $\mathbb K^n$ and $\B'={,b'_i\mid i\in I',}$ of $V$ and I define $$ c_i b'_i \mapsto b_i$$

    Wouldn't this be a description of an isomorphism without picking an ordering?

    – learner Dec 14 '14 at 02:25
  • @learner: I suppose "unspecified orderings" should be read as "unordered bases". But your definition does not work, since $b'i$ is defined for $i\in I'$, but then $b_i$ is not defined, since it requires $i\in I$. (Using $J$ instead of $I'$ and writing $j\in J$ this is more obvious.) You would need bases in $V,K^n$ indexed by the _same set. But $K^n$ comes equipped with a standard basis indexed by ${1,\ldots,n}$ (which is what sets $K^n$ apart from other spaces). Using a basis indexed by ${1,\ldots,n}$, or by a set with a chosen bijection to that set, amounts to using an ordered basis. – Marc van Leeuwen Dec 14 '14 at 06:09
  • 2
    I consider the start of your post as confusing (possibly even wrong). Whats is ${b_1,b_2, \dots , b_n}$ a set or something else? If something else, what is it and how can one know? If the former, is ${b_1,b_2}$ the same or not as ${b_2,b_1}$? What about ${1,2}$ and ${2,1}$? When basis are automatically assumed to be ordered they are usually not defined and denoted as sets but as families/n-tuples/sequences. If a basis is defined as a set it ought to be assumed as not ordered. – quid Dec 14 '14 at 12:46
  • 1
    @quid: Of course ${b_1,\ldots,b_n}$ denotes a set, I never claim the contrary. But by indexing the elements like that you have also specified an ordering, for instance you have $b_1$ as preferred first element. The definition of a map in the question depends on that choice: if you take the same set of vectors but index them differently you get a different isomorphism. Try starting "Given a basis $\mathcal B\subset V$, one defines an isomorphism" and you'll see that you cannot continue without choosing names for the elements of $\cal B$ first. So what you are using is an ordered basis. – Marc van Leeuwen Dec 14 '14 at 13:56
  • It seems my point was not clear. What if I say let $B= {b_2, b_1}$ be a basis. Which is the first and which is the second element of the basis? My point is you should not use a set there. But a tuple $(b_1, \dots, b_n)$ or just a list as in the question. To use set notation is confusing. – quid Dec 14 '14 at 14:00
  • 2
    @quid Yes, then I guess we agree completely. It is better to talk about a tuple or list, and by using the term "ordered basis" the book is stressing that it is doing just that. What I wanted to say is that even if your sentence should appear to mention only a set, but at the same time introduces a numbering of the elements, it is in fact introducing (choosing) an ordered basis. I'll rewrite that a bit for clarity though. – Marc van Leeuwen Dec 14 '14 at 15:02
  • I agree we seem to agree. :) Yes, often implicitly an ordering is there even if one just talks about a set. What I meant to stress is that an ordered basis is not only ordered by the virtue of the naming of the elements. But if one is strict they are really different mathematical objects, the ordered one a tuple or family, the not ordered one a set. Thus I did not quite like you using set notation at the start. But in general I find your answer very good. – quid Dec 14 '14 at 15:08
  • @MarcvanLeeuwen Okay, I get it. I was going to say I can let $I = {1, \dots, n}$ but the problem is that then the index set is ordered and then ${b_i}{i \in I}$ will have the induced order. A basis ${b_i}{i \in I}$ is only unordered it the index set $I$ is unordered, right? – learner Dec 16 '14 at 01:13
  • Very very good answer, btw. – learner Dec 16 '14 at 01:14
1

Edit: Ignore this answer, it is incorrect. I am saving this answer for the sake of the comments, but Marc's answer and reasoning are correct.

  1. Not usually. In most texts, you should not assume a basis is ordered if it is not expressly said to be. Writing $b_1,\ldots,b_n$ is usually not an order, though some writers (including me) will sometimes use $(b_1,\ldots,b_n)$ to indicate an ordered basis (because it's an ordered $n$-tuple).

  2. The order is indeed irrelevant in the above isomorphism. The point is that there is no canonical isomorphism between finite-dimensional vector spaces and $\mathbb{K}^n$. You can always define an isomorphism by taking an unordered basis $v_1,\ldots,v_n$ of $V$ and an unordered basis $k_1,\ldots,k_n$ of $\mathbb{K}^n$, and specifying that $v_i \mapsto k_i$. The ordering only matters if you're doing things like writing down the matrix of a transformation; then different orderings of the same basis result in different matrices. The ordering isn't relevant if you're only defining a linear transformation (unless, of course, you're using a matrix to do so.)

  3. The most likely reason why the author is choosing to define this particular isomorphism is to cut down on notation. It has the notational advantage that the moment you specify an ordered basis, there is also a specified isomorphism to $\mathbb{K}^n$; therefore you don't have to go about defining the isomorphism every time you have a new basis. But from a strictly mathematical viewpoint there is no advantage whatsoever.

Gyu Eun Lee
  • 18,793
  • 1
    I find this answer misleading. Just by calling the basis vectors $b_1,\ldots,b_n$, one is choosing an order on them. In some contexts one could say ${b_1,\ldots,b_n}$ to indicate order does not matter there, but if any $b_i$ is used in an expression, that expression uses an ordered basis. In particular in your point 2, you are using ordered bases of $v_i\in V$ and $k_i\in K^n$, which allows writing $v_i\mapsto k_i$ to specify a linear map. Try doing it with bases ${,v_i\mid i\in I,}$, ${,k_j\mid j\in J,}$ of $V$, $K^n$, given only that $|I|=|J|=n$ (and without further choices). – Marc van Leeuwen Dec 13 '14 at 06:11
  • @MarcvanLeeuwen So in infinite dimension, like if $H$ is a Hilbert space and $b_n$ is a basis sequence, this sequence is ordered because we enumerate it? – learner Dec 13 '14 at 06:14
  • 1
    @MarcvanLeeuwen I think you're missing the point of 2. An order has nothing to do with being able to use $v_i\mapsto k_i$ to define a linear map. I can easily reindex the $v_i$, say by a new set of indices $I$ with no ordering on I, and define the same linear map by $v_\alpha\mapsto k_\alpha$ for each $\alpha\in I$. This shows that we can define the map irrespective of any ordering on the bases, and indeed in practice when one defines a linear transformation by its action on the basis one doesn't worry about the ordering. – Gyu Eun Lee Dec 13 '14 at 06:40
  • This suggests that a Hilbert space basis has to be ordered (because the sequence may only converge conditionally) – learner Dec 13 '14 at 06:44
  • A Hilbert space basis is very different from an algebraic basis. Defining a linear transformation like I have described above does not necessarily result in a bounded linear operator, for one thing. This discussion should be limited to finite dimensions. – Gyu Eun Lee Dec 13 '14 at 08:46
  • 1
    @neuguy: I think there are two interpretations of "ordered basis" at issue here. One is having a total ordering first to last; I agree one can do without that. But you are implicitly using a fixed indexing set $I$ for $|I|=n$ for all bases of $n$-dimensional spaces, which you need to define your map. While there is no absolute first and last, I would still this using ordered bases; point is, you are not just giving an unlabelled set of vectors. Properly unordered basis would use distinct index sets for each basis; that's why I said (unrelated) $I,J$; you cannot define an iso then. – Marc van Leeuwen Dec 13 '14 at 09:17
  • The use of a universal index set $I$ is only marginally different from using $I={1,\ldots,n}$, as most do. Once you fix an ordering of $I$, it amounts to exactly the same thing. It is actually quite hard to find for each $n$ a single special set $I$ of $n$ elements that does not come with a natural total ordering on it. So for practical purposes there is not much difference from taking $I={1,\ldots,n}$. – Marc van Leeuwen Dec 13 '14 at 09:20
  • @MarcvanLeeuwen Sorry, this may be a philosophical difference, but I don't see where the order comes into play with a universal indexing set. And even if we use two distinct indexing sets, this is in finite dimensions; there are $n!$ possible bijections from $I$ to $J$, and there is nothing preventing us from choosing one of them, which amounts to defining the isomorphism. Surely the existence of a bijection from $I$ to $J$ doesn't depend on whether these are ordered sets? – Gyu Eun Lee Dec 13 '14 at 09:27
  • The point is exactly choosing. To fix an isomorphism, one must choose something, and the choice always and exactly amounts to choosing an ordered basis in $V$. Even if you try to do it using another method. There is a natural bijection between isomorphisms $V\to K^n$ and ordered bases in $V$. There is no such bijection for unordered bases. Period. – Marc van Leeuwen Dec 13 '14 at 11:05
1

Here are some more aspects around ordered bases.

In order to motivate my point of view I'd like to go through a few paragraphs of Serge Lang's Linear Algebra and through Steven Roman's Advanced Linear Algebra. I selected them as an example of (well-known) authors which do not explicitely introduce ordered bases (S.Lang) and which explicitely do so (S. Roman).

It's somewhat easier to start with:

First Part: Steven Roman Explicit definition of ordered basis

Steven Roman introduces basis and ordered basis separately. This indicates that they are two different concepts. The definition of basis is a follow-up of Theorem 1.7:

Theorem 1.7: Let $S$ be a set of vectors in $V$. The following are equivalent:

1) $S$ is linearly independent and spans $V$.

2) Every nonzero vector $v\in V$ is an essentially unique linear combination of vectors in $S$.

3) $S$ is a minimal spanning set, that is, $S$ spans $V$ but any proper subset of $S$ does not span $V$.

4) $S$ is a maximal linearly independent set, that is, $S$ is linearly independent, but any proper superset of $S$ is not linearly independent.

A set of vectors in $V$ that satisfies any (and hence all) of these conditions is called a basis for $V$.

By going through 1) to 4) we see in fact four different definitions of the term basis (and all are equivalent of course). But in none of them there is explicitely a notion of order used to define the term basis. Noticeable is the formulation essentially unique linear combination in 2). This term is previously defined by S.Roman as follows:

Definition: Let $S$ be a nonempty set of vectors in $V$. To say that a nonzero vector $v\in V$ is an essentially unique linear combination of the vectors in $S$ is to say that, up to order of terms, there is one and only one way to express $v$ as a linear combination $$v=a_1s_1+\cdots+a_ns_n$$ where the $s_i$'s are distinct vectors in $S$ and the coefficients $a_i$ are nonzero.

Now all terms in theorem 1.7 seem to be clear and also the term essentially unique does not need any kind of ordering for its definition (in fact it explicitely excludes it with the phrase ... up to order of terms ...).

A few pages later we find the section:

Ordered Bases and Coordinate Matrices

It will be convenient to consider bases that have an order imposed on their members.

Definition: Let $V$ be a vector space of dimension $n$. An ordered basis for $V$ is an ordered $n$-tuple $(v_1,\ldots,v_n)$ of vectors for which the set $\{v_1,\ldots,v_n\}$ is a basis for $V$.

If $\mathcal{B}=(v_1,\ldots,v_n)$ is an ordered basis for $V$, then for each $v\in V$ there is a unique ordered $n$-tuple $(r_1,\ldots,r_n)$ of scalars for which $$v=r_1v_1+\ldots r_nv_n$$

Accordingly, we can define the coordinate map $\phi_{\mathcal{B}}:V\rightarrow F^n$ by

\begin{equation*} \phi_{\mathcal{B}}(v)=[v]_{\mathcal{B}}= \begin{bmatrix} r_1\\ \vdots\\ r_n \end{bmatrix} \end{equation*}

We clearly see that basis and ordered basis are two different concepts. On the one hand the notion $$\{v_1,\ldots,v_n\}$$ despite the suggestive index notation does not imply an ordered basis. We have to additionaly append the concept of an $n$-tuple $(v_1,\ldots,v_n)$ which carries a corresponding ordering.

On the other hand we also see that the crucial things are coordinates and their description via $n$-tuples, which are ordered objects. So whenever we do some things where a coordinate map is involved, we need explicitely or implicitely an ordered basis in order to respect the order of $n$-tuples of coordinates.

The suggestive index notation is merely a convenient description of the basis elements to easily add an ordering on the basis in case we want to use it.

Second Part: Serge Lang No explicit definition of ordered basis

You may wonder, if there is no explicit definition of an ordered basis, how can S. Lang introduce coordinate maps? Let's look what he says. He introduces the term basis as follows:

If elements $v_1,\ldots,v_n$ of $V$ generate $V$ and in addition are linearly independent, then $\{v_1,\ldots,v_n\}$ is called a basis of $V$. We shall also say that the elements $v_1,\ldots,v_n$ constitute or form a basis of $V$.

He continues with:

We shall now define the coordinates of an element $v\in V$ with respect to a basis. The definition depends on the following fact:

Theorem 2.1: Let $V$ be a vector space. Let $v_1,\ldots,v_n$ be linearly independent elements of $V$. Let $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ be numbers. Suppose that we have $$x_1v_1+\cdots+x_nv_n=y_1v_1+\cdots+y_nv_n.$$ Then $x_i=y_i$ for $i=1,\ldots,n$.

This theorem which is a preparation in order to introduce coodinates does not imply any order of the elements $v_1,\ldots,v_n$. It solely uses the property that each basis element is uniquely identified by its index. Observe, that we do not use $n$-tuples like $(x_1,\ldots,x_n)$, but instead $n$ uniquely identifiable elements $x_1,\ldots,x_n$ which do not need any ordering. S.Lang continues as follows

Let $V$ be a vector space, and let $\{v_1,\ldots,v_n\}$ be a basis of $V$. The elements of $V$ can be represented by $n$-tuples relative to the basis, as follows. If an element $v$ of $V$ is written as a linear combination $$v=x_1v_1+\cdots+x_nv_n$$ then by the above remark, the $n$-tuple $(x_1,\ldots,x_n)$ is uniquely determined by $v$. We call $(x_1,\ldots,x_n)$ the coordinates of $v$ with respect to our basis and we call $x_i$ the $i$-th coordinate. The coordinates with respect to the ususal basis $E_1,\ldots,E_n$ of $K^n$ are the coordinates of the $n$-tuple $X$. We say that the $n$-tuple $X=(x_1,\ldots,x_n)$ is the coordinate vector of $v$ with respect to the basis $\{v_1,\ldots,v_n\}$.

Although S.Lang does not explicitely introduce the term ordered basis, the construction of the coordinate vector $X$ which is an (ordered) $n$-tuple imposes implicitely an ordering of the basis vectors $\{v_1,\ldots,v_n\}$. So, from now on we have two different flavours of a basis. Basically a basis is defined without notion of ordering. But whenever coordinates come into play, they impose an ordering on the basis.

We now take a look at two examples to further clarify the role of ordering of a basis, which is per se defined without ordering. First we look at example 6:

Example 6: Show that the vectors $(1,1)$ and $(-1,2)$ form a basis of $\mathbb{R}^2$.

We have to show that they are linearly independent and that they generate $\mathbb{R}^2$.

In this example there is no ordering of the basis elements specified or necessary. We simply have to show linear independence and that they span $\mathbb{R}^2$. We may name the vectors $v_1=(1,1)$ and $v_2=(-1,2)$ and use a basis $$B=\{v_1,v_2\}$$ But here any ordering suggested by the index notation is irrelevant. We could e.g. rename the vectors $v_1=(-1,2)$ and $v_2=(1,1)$ and again consider the basis $B=\{v_1,v_2\}$. In fact we are free to rename them as $a_3=(1,1)$ and $\alpha_y=(-1,2)$ and work with $$B=\{a_3,\alpha_y\}$$ but this would be not wise, cause this representation is not convenient. In case we want to do some further calculations where coordinates are involved, the naming via $v_1,v_2$ is much more benefical, because then we do need an ordering and we are already well prepared with the help of the proper index notation.

One more example:

Example 3: Let $V$ be the vector space of functions generated by the two functions $e^t,e^{2t}$. Then the coordinates of the function $$3e^t+5e^{2t}$$ with respect to the basis $\{e^t,e^{2t}\}$ are $(3,5)$.

The coordinate vector of $3e^t+5e^{2t}$ with respect to the basis $\{e^t,e^{2t}\}$ is stated as $(3,5)$. We observe: The basis is per se not ordered. We also have no indication of ordering via index-notation. But it seems, that the position of the elements in the basis indicate some ordering. In fact it's convenient to interpret it this way.

But the relevant indication of order is the coordinate $(3,5)$ itself, which necessarily implies that the first coordinate $x=3$ is associated with the basis vector $e^t$ and the second coordinate $y=5$ is associated with the basis vector $e^{2t}$.

In fact, S.Lang presumably wrote $(3,5)$ since its convenient to assume an ordering of the basis elements from left to right. If in another culture the preferred reading direction is from right to left, the author might use a coordinate vector $(5,3)$ instead. Both are correct, since there is no predefined ordering within the basis. But, when determining once a coordinate vector the ordering is from then on determined.

Conclusion: The usual definition of a basis does not include any ordering. But, whenever coordinates come into play, we need the concept of ordering. This can be done either by explicitely defining an ordered basis, or by implicitly imposing an ordering on a basis. In the second case it's a matter of convenience to relate the ordering of the basis to that of $\mathbb{N}$ via a proper index notation. It's also convenient, if basis vectors are given by values (as in Example 3) to assume an ordering from left to right.


Regarding OPs questions:

(1) Are all finite dimensional bases in linear algebra courses in general automatically assumed to be ordered because writing $b_1, \dots, b_n$ is an order?

According to the conclusion above the answer is no. But, if we have to use coordinates, an ordering has to be additionaly imposed either explicitely via ordered bases or implicitely. In both cases a suggestive ordering of the index notation is usually used for convenience.

(2) It seems to me that the order is irrelevant in the sense that the isomorphism above could just as well map $(c_1 v_1 + \dots + c_n v_n) \mapsto (c_n, \dots, c_1)$. Hence my question: is it possible to give an isomorphism without using an ordered basis?

Again the answer is (essentially) no. Whenever we use within the proof some kind of coordinates, we have to use an ordering of the basis (explicitly or implicitely).

It is correct to say, that we are not forced to assume an ordering $(v_1,v_2,\ldots,v_n)$ but could instead use another isomorphism with another ordering. But, we always have to be careful to precisely specify the type of ordering.

Markus Scheuer
  • 108,315