We are now ready to introduce one of the most elegant results in algebra, the Galois correspondence. This correspondence gives us a framework for understanding the relationships between the structure of a splitting field over a field K and the structure of its group of automorphisms over K. Once we establish this correspondence, we go on to study in some detail how the group provides some distinguishing characteristics of the various conjugates over K of an element of the splitting field.

Normal Field Extensions and Splitting Fields

The property of splitting fields that encapsulates much of the information necessary for proving steps in the Galois correspondence is that of normality. In this section, we introduce the property and explore its connection with splitting fields.

Definition 23.1 (Normal Field Extension in ℂ). Let K be a subfield of ℂ. An algebraic field extension L/K is normal if every polynomial f ∈ K[X] that is irreducible over K and that has at least one root in L contains n = deg(f) roots in L.

Note that since the roots of an irreducible polynomial in K[X] are distinct (Theorem11.3), this definition is equivalent to

Definition 23.2 (Normal Field Extension). An algebraic field extension L/K is normal if every polynomial p ∈ K[X] that is irreducible over K and that has at least one root in L factors into linear terms over L.

Clearly a splitting field of an irreducible polynomial p ∈ K[X] satisfies the condition for the particular polynomial p, but the interest of the property lies in whether the condition is satisfied for all irreducible polynomials q ∈ K[X]: each such polynomial must have either none of its roots in L or all of its roots in L.

We have established that the subspaces in a Hilbert Space are in 1:1 correspondence with the projectors onto that space, that is, to each subspace there corresponds a projection and vice versa. In the previous chapters we have shown how subsets and artificial classes give us a semantics for rudimentary retrieval languages. What we propose to do next is to investigate a semantics based on subspaces in a Hilbert space and see what kind of retrieval language corresponds to it. In particular we will be interested in the nature of conditionals.

To appreciate the role and value of conditionals in IR we look a little more about how they arise in the application of logic to IR. When retrieval is modelled as a form of inference it becomes necessary to be explicit about the nature of conditionals. It is simplest to illustrate this in terms of textual objects. A document is seen as a set of assertions or propositions and a query is seen as a single assertion or proposition. Then, a document is considered relevant to a query if it implies the query. The intuition here is that when, say, q is implied by document Δ, then Δ is assumed to be about q. Although retrieval based on this principle is possible, it is not enough. Typically, a query is not implied by any document leading to failure as in Boolean retrieval. To deal with this a number of things can be done.

In this chapter an elementary introduction to simple information retrieval is given using set theory. We show how the set-theoretic approach leads naturally to a Boolean algebra which formally captures Boolean retrieval (Blair, 1990). We then move onto to assume a slightly more elaborate class structure, which naturally leads to an algebra which is non-Boolean and hence reflects a non-Boolean logic (see Aerts et al., 1993, for a concrete example). The chapter finishes by giving a simple example in Hilbert space of the failure of the distribution law in logic.

Elementary IR

We will begin with a set of objects; these objects are usually documents. A document may have a finer-grained structure, that is, it may contain some structured text, some images and some speech. For the moment we will not be concerned with that internal structure. We will only make the assumption that for each document it is possible to decide whether a particular attribute or property applies to it. For example, for a text, we can decide whether it is about ‘politics’ or not; for images we might be able to decide that an image is about ‘churches’. For human beings such decisions are relatively easy to make, for machines, unfortunately, it is very much harder. Traditionally in IR the process of deciding is known as indexing, or the assigning of index terms, or keywords. We will assume that this process is unproblematic until later in the book when we will discuss it in more detail.

This appendix will give a brief, highly simplified introduction to a number of the principles underlying quantum theory. It is convenient to collect them here independent of information retrieval. We will use the Dirac notation introduced in the previous appendix to express the necessary mathematics. Before examining the few principles underlying quantum mechanics let us make two comments. The first is that there is no general agreement about whether probabilistic quantum statements apply to individual isolated systems or only to ensembles of such systems identically prepared. The second comment is that there is no distinct preference whether to develop quantum theory fully in terms of vectors in a Hilbert space, or in terms of the density operators applied to that space. We will not take a strong position on either division. For convenience we will assume that statements are applicable to single systems, and that when it suits, either vectors or density operators can be used.

To begin with we will consider only pure states of single systems and observables with discrete non-degenerate spectra. This will keep the mathematics simple.

There are four significant fundamental concepts to consider: physical states, observables, measurements and dynamics; and of course the interplay between these.

This book begins and ends in information retrieval, but travels through a route constructed in an abstract way. In particular it goes through some of the most interesting and important models for information retrieval, a vector space model, a probabilistic model and a logical model, and shows how these three and possibly others can be described and represented in Hilbert space. The reasoning that occurs within each one of these models is formulated algebraically and can be shown to depend essentially on the geometry of the information space. The geometry can be seen as a ‘language’ for expressing the different models of information retrieval.

The approach taken is to structure these developments firmly in terms of the mathematics of Hilbert spaces and linear operators. This is of course the approach used in quantum mechanics. It is remarkable that the application of Hilbert space mathematics to information retrieval is very similar to its application to quantum mechanics. A document in IR can be represented as a vector in Hilbert space, and an observable such as ‘relevance’ or ‘aboutness’ can be represented by a Hermitian operator. However, this is emphatically not a book about quantum mechanics but about using the same language, the mathematical language of quantum mechanics, for the description of information retrieval. It turns out to be very convenient that quantum mechanics provides a ready-made interpretation of this language.

In the previous chapters we have introduced set-theoretic, logical and algebraic notions, all of which can be used profitably in IR. We now wish to broaden the discussion somewhat and attempt to introduce a language and a notation for handling these disparate notions within a single space, viz. Hilbert space (Simmons, 1963), thereby constructing a probability measure on that space via its geometry. At first glance this appears to be a difficult task, but if we consider that much IR research has been modelled in finite vector spaces (Salton, 1968) with an inner product, many of our intuitions for that can be transferred to the discussion based on Hilbert spaces. One major reason for adopting the more abstract point of view is that we wish to present a ‘language’ for describing and computing objects, whether text, image or speech, in a general way before considering any particular implementation.

The language introduced uses a small set of operators and functions, and the notation will be the Dirac notation (Dirac, 1958). Although at first sight the Dirac notation strikes one as confusing and indeed awkward for learning about linear algebra, its use in calculating or computing simple relationships in Hilbert space is unparalleled. Its great virtues are that any calculation is simple, the meaning is transparent, and many of the ‘housekeeping’ rules are automatically taken care of. We will demonstrate these virtues as we progress.

This book is about underlying ideas and theory. It is about a way of looking, and it is about a formal language that can be used to describe the objects and processes in Information Retrieval. It is not about yet another model for IR, although perhaps some will want to find such an interpretation in it.

Why do we need another way of looking at things? There are some good reasons. Firstly, although there are several IR models, for example vector space, probabilistic, logical to name the most important, they cannot be discussed within a single framework. This book, The Geometry of Information Retrieval (GIR), is a first attempt to construct a unifying framework. Secondly, although many of us pay lip-service to the conceptual depth of some of the fundamental notions in IR such as relevance, we rarely analyse these notions formally to any bedrock. This is not because we are lazy, it is rather because our theoretical tools have made it very difficult to do so. What follows will, it is hoped, aid such formal analysis. And thirdly, there is a need to support the formal specification or expression of IR processes so that we can formally reason about them. For example, we need to be able to lay down mathematical constructs that will direct us in the design of some new algorithms for IR. This is especially important if we wish to extend the boundaries of current research.

In this chapter we introduce methods for solutions of the standard eigenvalue problem

Ax = λx,

where A is a square n × n matrix, as well as for generalized eigenproblems. The main theory is based on the solvers of the previous chapter for linear systems. Unlike, however, the methods of the previous chapter where both direct and iterative approaches are effective, in eigenvalue problems only iterative solvers are efficient. We start with the simple power method and its variants, and we proceed with more sophisticated methods including a method for nonsymmetric eigenproblems using the Arnoldi iteration. We classify the different eigensolvers as local or global depending on whether they are typically used to compute one or two eigenvalues or the entire spectrum, respectively.

We introduce one new MPI function, MPI_Alltoall, and demonstrate its use through some of the algorithms presented in this chapter. In addition, we reiterate the use of MPI_Allgather and MPI_Allreduce through example implementations of algorithms.

LOCAL EIGENSOLVERS

We have already seen in Chapter 2 that computing the eigenvalues accurately from the determinant may not always be possible. The Newton-Raphson method of Chapter 4 is an accurate method of computing the roots of the characteristic polynomial, but it can be extremely inefficient for large systems. In the following, we present a simple method to compute iteratively the maximum and minimum eigenvalues and corresponding eigenvectors. We can also compute any other eigenvalue for which we have a good initial guess.