Motivation: Leavitt and Cuntz Algebras

To a row-finite directed graph E we associate two algebras: the graph C*-algebra Cfi(E), and the Leavitt path algebra Lk(E) when k is a field. These are defined using nearly identical generators and relations, and LC(E) turns out to be to a dense subalgebra of Cfi(E). Defining an algebra by generators and relations is quite easy | take a quotient of a free algebra | but it is more difficult to construct universal C*-algebras. Thus the construction of Cfi(E) is specialized. Our first goal is to define Cfi(E) and establish some basic properties, and then we use that construction to motivate the definition of Lk(E).

In [18], Leavitt introduced rings L = Ln, deøned by generators and relations, with the mal function that L ' Ln as right L-modules but L;L2; : : : ;Ln�1 are pairwise nonisomorphic. Independently, Cuntz [10] studied the C*-algebras On generated by isometries satisfying similar relations as in Leavitt's algebras Ln. Nowadays it is wellknown that Ln is naturally a dense subalgebra of On. In this section we highlight Leavitt's reasons for inventing Ln, and how Ln øts into the more general class of Leavitt path algebras.

A unital ring R has invariant basis number (or ibn) if, whenever Rm ' Rn as right R-modules, necessarily m = n. For such R, the rank of a free R-module can be deøned to be the cardinality of a basis. Any øeld has ibn, since a vector space over a øeld has a uniquely determined dimension. In fact all division rings have ibn for the same reason. Any commutative (unital) ring R has ibn: if m is a maximal ideal of R and Rn is any free R-module, then Rn R (R=m) ' (R=m)n as (R=m)-modules. But (R=m) is a øeld, so the dimension n is uniquely determined. More generally, whenever we have a unital ring homomorphism R ! k and k has ibn, then R must also have ibn (same proof as above). Thus the class of ibn rings is quite large | but not all rings have ibn. Example. [16] Let V be an inønite-dimensional vector space over a øeld and let R = End(V ) be the ring of linear endomorphisms V ! V . Then any isomorphism ' : V ' V ø V induces an isomorphism of vector spaces R = Hom(V; V ) ' Hom(V; V ø V ) ' Hom(V; V ) ø Hom(V; V ) = R2: But in fact one checks easily that it is an isomorphism of right R-modules, and so we see R ' R2 ' R3 ' ø . So R spectacularly fails to have ibn. We've seen two extremes: ibn rings, versus rings with R ' R2. Is there a middle ground? For instance, is it possible that R ' R2 6' R3? Of course, once R ' R3 we necessarily have R2 ' R4 ' R6 ' so we can't expect to have arbitrarily wild isomorphisms between free modules. In [18], Leavitt introduces the module type of a ring R which fails ibn. Let m be the _rst integer such that Rm ' Rn for some n > m, and let n be the smallest with this property; the pair (m; n) is called the module type of R. Thus in the ring R = End(V ) in the above

1 ∗ i i

1 ∗

Proposition. Let R be a unital ring. Then R Rn if and only if R has elements x1, . . . , xn, x∗, . . . , xn satisfying the relations (CK1) x∗xi = 1, and x∗xj = 0 for i = j, (CK2) 1 = x1x∗ + · · · + xnxn. Proof. If R Rn, then R has a basis {x1, . . . , xn} as a right R-module. Then we may write 1 := x1x∗ + · · · + xnxn for some x∗ ∈ R. Note that multiplying on the left by xj gives xj = x1(x∗xj) + · · · + xn(xnxj)

It was Garrett Birkhoff‘s work in the mid thirties that started the general development of lattice theory. In a Brilliant series of papers he demonstrated the importance of the lattice theory and showed that it ii provides a unifying framework for previously unrelated developments in any mathematical disciplines. During a pivot step, we make the value of a nonbasic variable just large enough to get the value of a basic variable down to zero. This, however, might never happen. If we now try to bring x2 into the basis by increasing its value, we notice that none of the tableau equations puts a limit on the increment. We can make x2 and z arbitrarily large the problem is unbounded. By letting x2 go to infinity we get a feasible half line - starting from the current BFS - as a witness for the unbounded ness. In our case this is the set of feasible solutions Such a halfline will typically be the output of the algorithm in the unbounded case. Thus, unboundedness can quite naturally be handled with the existing machinery. In the geometric interpretation it just means that the feasible polyhedron P is unbounded in the optimization direction. While, we can make some nonbasic variable arbitrarily large in the unbounded case, just the other extreme happens in the degenerate case: some tableau equation limits the increment to zero so that no progress in z is possible. The only candidate for entering the basis is x2, but the first tableau equation shows that its value cannot be increased without making x3 negative. This may happen whenever in a BFS some basic variables assume zero value, and such a situation is called degenerate. Unfortunately, the impossibility of making progress in this case does not imply optimality, so we have to perform a `zero progress' pivot step. In our example, bringing x2 into the basis results in another degenerate tableau with the same BFS. Nevertheless, the situation has improved. The nonbasic variable x1 can be increased now, and by entering it into the basis, we already obtain the final tableau With optimal BFS x = (x1 ……..x4) = (2,2,0,0) In this example, after one degenerate pivot we were able to make progress again. In general, there might be longer runs of degenerate pivots. Even worse, it may happen that a tableau repeats itself during a sequence of degenerate pivots, so the algorithm can go through an infinite sequence of tableaus without ever making progress. This phenomenon is known as cycling, and an example can be found. If the algorithm does not terminate, it must cycle. This follows from the fact that there are only finitely many different tableaus.

and assume there is another tableau T 0 with the same basic and non-basic variables, i.e. T is the system By the tableau properties, both systems have the same set of solutions. Therefore must hold for all d-vectors xN, and this implies T = T‘ There are two standard ways to avoid cycling: Bland's smallest subscript rule: If there is more than one candidate xk for entering the basis or more than one candidate for leaving the basis, which is another manifestation of degeneracy, choose the one with smallest subscript k. Avoid degeneracies altogether by symbolic perturbation. By Bland's rule, there is always a way of escaping from a sequence of degenerate pivots. For this, however, one has to give up the freedom of choosing the entering variable. For us it will be crucial not to restrict the choice of the entering variable, so we will abandon Bland's rule and instead resort to the method of symbolic perturbation, although this requires more computational effort. In 1854, George Boole (1815–1864) introduced an important class of algebraic structures in his research work on mathematical logic. In his honor these structures have been called Boolean algebras. These are special type of lattices. In particular, congruence lattices play an important role. It was E. Schroder, who about 1890, considered the lattice concept in today‘s sense. At approximately the same time, R. Dedikind developed a similar concept in his work on groups and ideals. Dedikind defined modular and distributive lattices which are types of lattices of that are important in applications. The rapid development of lattice theory started around 1930. We could say that Boolean lattices or Boolean algebras are the simplest and at the same time the most important lattices for applications. It was Garrett Birkhoff‘s work in the mid thirties that started the general development of lattice the importance of the lattice theory and showed that it ii provides a unifying framework for previously unrelated developments in any mathematical disciplines. During a pivot step, we make the value of a nonbasic variable just large enough to get the value of a basic variable down to zero. This, however, might never happen. If we now try to bring x2 into the basis by increasing its value, we notice that none of the tableau equations puts a limit on the increment. We can make x2 and z arbitrarily large the problem is unbounded.+

Adler (2010). Abstract Polytopes, PhD Thesis, Department of Operations Research, Stanford University, Stanford, California. Adler and N. Megiddo (2010). A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension. J. ACM. Adler and R. Saigal (2011). Long Monotone Paths in Abstract Polytopes. Mathematics of Operations Research. Borceux F. (2011). Handbook of categorical algebra volume I, II, III, Cambridge University Press. Coquand, T. About Stone‘s notion of Spectrum, Journal of Pure and Applied Algebra, volume 197, 2010. Coquand, T.; Spitters, B. (2009). Formal topology and constructive mathematics: the Gelfand and StoneYosida representation theorems, Journal of Universal Mathematics. Coquand, T.; Spitters, B. (2012). An elementary constructive proof of Gelfand duality for C*-algebras, submitted for publication. D. Avis and V. Chvatal (2010). Notes on Bland's pivoting rule. Math. Programming Study, 8: pp. 24-3. B. Bixby. Personal communication. Goldblatt, R. (2011). Topoi, the categorical analysis of logic, Elsevier Science Publishers. Hartshorne, R. (2010). Algebraic Geometry (8th edition), Springer-Verlag. J. Blomer (2010). How to denest Ramanujan's nested radicals. In Proceedings of 33rd Annual Symposium on Foundations of Computer Science.

Computer Science. K. H. Borgwardt (2010). The Simplex Method-A Probabilistic Analysis, volume 1 of Algorithms and Combinatorics, Springer-Verlag, Berlin Heidelberg, New York. N. Amenta (2011). Helly Theorems and Generalized Linear Programming. PhD thesis, University of California at Berkeley. V. Chvatal (2013). Linear Programming. W. H. Freeman, New York.

M.Sc. (Mathematics), CSIR – JRF Qualified