Cyprien Richer
email: cyprien.richer@cerema.fr

Sophie Hasiak
email: sophie.hasiak@cerema.fr

Special Issue "Has rail saved the city? -Rail and Urban Development in Comparative Perspective" Territorial opportunities of tram-based systems: Comparative analysis between Nottingham (UK) and Valenciennes (FRA)

Keywords: tramway, urban planning, transport assessment, urban regeneration, public transport

Within the European project « Sintropher », this paper focuses on a comparative analysis between two tramway systems in Nottingham (UK) and Valenciennes (FRA). The aim is to understand how these tram-based systems were successfully integrated in the urban areas. Firstly, we describe the national contexts concerning assessments of urban public transport policies. Secondly, we analyse these tram projects, and especially their territorial dynamics. Thirdly, we have a look at urban transformations that occurred around their terminal stations in Hucknall and Denain.

Introduction

« Sintropher » 1 is an European project whose goal is to promote the development of new tramway services and to improve existing ones located in intermediate or suburban regions of Northwest Europe. It is in this context that the study led by CETE Nord-Picardie, subpartner of the authority in charge of urban public transport in the region of Valenciennes (SITURV), takes place. Based on different European tram-based systems 2 , the work compares decision-making and assessment processes in six different countries: Germany (Saarbrucken), the United Kingdom (Nottingham), France (Valenciennes), The Netherlands (Utrecht), Spain (Velez-Malaga) and Italy (Bergamo). This paper specifically refers to the first modern tramway lines in Nottingham (opened in 2004) and in Valenciennes (opened in 2006Valenciennes (opened in -2007)). The aim is to understand how these tram-based systems were successfully integrated in the urban area. Specifically, we highlight the territorial opportunities disclosed by tram-based systems and explain how actors seize them.

There is a growing body of scientific researches based on regenerative effects of light rail investment policies (trams in particular). Tramways are usually considered as key tools for sustainable development [START_REF] Frenay | Le Tram, outil en faveur d'une ville durable ?[END_REF][START_REF] Stambouli | Les territoires du tramway moderne : de la ligne à la ville durable[END_REF]. However, analysing the impact of this transport service on the territorial economy raises some serious methodological difficulties [START_REF] Offner | Les effets structurants du transport : mythe politique, mystification scientifique[END_REF]. The mechanism which links the new public transport system to the economic development is not clear [START_REF] Mackett | The impact of new urban public transport systems: will the expectations be met ?[END_REF]. All the methodologies which try to isolate transport effects, have weaknesses and some of them are quite simplistic and not suitable for an empirical context [START_REF] Hass-Klau C | Economic Impact of Light Rail Investments : Summary of the Results of 15 Urban Areas in France, Germany, UK and North America, Urban Transport Development[END_REF]. For several reasons, it has been proved that the effect of a light rail investment on land prices or economic development is generally modest [START_REF] Boucq | Assessment of the real estate benefits due to accessibility gains brought by a transport project: the impacts of a light rail infrastructure improvement in the Hauts-de-Seine department[END_REF][START_REF] Hass-Klau C | Economic Impact of Light Rail Investments : Summary of the Results of 15 Urban Areas in France, Germany, UK and North America, Urban Transport Development[END_REF]. [START_REF] Mackett | The impact of new urban public transport systems: will the expectations be met ?[END_REF] highlight that urban or economic development is not produced or generated by the transport system, but it simply results from a relocation. "It would be difficult, with the benefit of hindsight, 1 Sustainable Integrated Tram-based Transport Options for Peripheral European Regions, further information on: http://www.sintropher.eu/ 2 " This term refers to railway passengers transport networks in order to serve cities outskirts. It is quite similar to the English expression « light rail » or the French one « tram-train » because it refers to the interface between metro and tram systems in dense urban environments and regional railway networks.

to conclude that the cities that have introduced such systems would have been better off without them" (Hylen,Pharoah, 2002). The case of the "Supertram" project in Sheffield is very significant because it shows that the tram system did not lead to urban renewal projects despite the local attempts [START_REF] Mackett | New urban rail systems : a policy-based technique to make them more successful[END_REF]. And one of the reasons is an insufficient integration of both of the two projects (urban renewal project and tram project) [START_REF] Dabinett | Transport investment and regeneration, Sheffield: 1992-1997[END_REF][START_REF] Dabinett | Transport investment and regeneration, Sheffield: 1992-1997[END_REF]. Besides, some local actors hope that the transport systems will be able to galvanise major regeneration of cities centre and other areas, however we have to say that the evidence of direct causality between transport and urban regeneration is hard to prove (Hylen,Pharoah, 2002).

Understanding the complex interrelationships between a city and its networks suggests the use of a relevant vocabulary. Therefore we have chosen to use the terms of "territorial effects" or "opportunities" instead of the term of "impact" which refers to automatic relations. Beyond that, the concept of "congruence", popularised by [START_REF] Offner | Les effets structurants du transport : mythe politique, mystification scientifique[END_REF], refers specifically to the idea of mutual adaptation of transports and urban planning by taking into account preexisting structural trends. Under different conditions, transport investment may have a key role in the territorial organization ; transport investment is alone insufficient, and has to be combined with other pre-existing conditions [START_REF] Trinder | Economic Growth and Transport Infrastructure Appraisal in McQuaid RW[END_REF][START_REF]Linkages Between Infrastructure and Economic Growth[END_REF]. While the exact relationship between transport and economic growth remains ambiguous, [START_REF] Eddington | The Eddington Transport Study, Main report: Transport's role in sustaining the UK's productivity and competitiveness[END_REF] identifies a number of micro drivers of productivity on which transport project may have an effect (by improving travel time, reliability, cost, connectivity, comfort, safety, and security). Nevertheless, the first "ingredient" for succeeding these transport projects is the political will [START_REF] Babalik-Sutcliffe E | Urban rail systems: analysis of the factors behind success[END_REF]Hass-Klau and coll (2000, 2003[START_REF] Hass-Klau C | Economic impact of light rail: the results of fifteen urban areas in France, Germany, UK and North America[END_REF][START_REF] Crampton | Development Impacts of Urban Rail Transport[END_REF]. Widely discussed in the scientific literature, the political conditions are a key element in the success of the projects and their territorial integration [START_REF] Offner | Le tramway Saint-Denis-Bobigny entre enjeux et usages la décision à l'épreuve du territoire[END_REF][START_REF] Edwards | Developing new urban public transport systems. An irrational decision-making process[END_REF][START_REF] Hamman | Le tramway dans la ville. Le projet urbain négocié à l'aune des déplacements[END_REF][START_REF] Richer | Des tramways contre-nature ? Regards croisés sur les processus de décision des projets de TCSP de l'arc Sud de l'aire métropolitaine lilloise[END_REF].

Based on these inputs, we take into account three positions. Firstly, rather than adopting an assessment reasoning uppermost based on the individualization of direct consequences of tram projects, we have adopted the position that tram services could be considered as some opportunities, as political tools for local authorities [START_REF] Offner | Les effets structurants du transport : mythe politique, mystification scientifique[END_REF]. Then, we do not exclude any economic approach of these networks usefulness, but we reject an only economic approach : indeed, single econometric calculations, even updated ones, are not sufficient to analyse transport networks. Thirdly, we consider that the central elements of assessment are public or private actors, institutional or technical actors, who are able to report the risks, the goals and the opportunities of urban transport projects. We make the assumption that the tram is both a transport and an urban planning tool that its opportunity depends on urban policy choices. This paper is structured in three steps. Firstly, we describe the national contexts concerning assessments of urban public transport policies. This first step allows us to point out quite contrasting decision-making models in these two countries that can allow us to explain the different levels of enthusiasm for tram projects. The method is based on a scientific literature review about transport projects assessments in both countries. Then, we analyse these tram-based systems, and especially their territorial dynamics by using monographic works [START_REF] Lepers | Nottingham Express Transit : le(s) rôle(s) du tramway en milieu urbain et périurbain[END_REF][START_REF] Frère | Structuration intercommunale et rôle des politiques de transports publics dans le Valenciennois[END_REF]. In a chronological way, we review the project genesis, its objectives and the obstacles to its opening. Adopting a functional and spatial analysis on both tramways helps us to understand their customary proceedings but also their integration singularities. Next, we have a look at urban transformations that occurred around these tram-based systems. Particularly, we focus on local mutations around the terminus stations: Hucknall (Nottingham tram) and Denain (Valenciennes tram). Both cities are good examples to analyse the local actors role in the integration of these new infrastructures and to try to define what the urban planning tramway is.

1/ British and French tramways : two contrasting models

Evolution of cities with tramway services

In the early 20 th century, all the big cities in each country implemented one or more tramway lines. This golden age lasted until the First World War that represented a "turning point in tramways history" [START_REF] Paris | Désiré, puis haï, et enfin adulé : les tribulations du tramway dans les villes de France[END_REF]. In the 1920s, dismantling of tramlines thus quickened in France and mainly in the United Kingdom. So, at the end of the Second World War, tramways remained in less than ten British big cities. The "Nottingham Corporation Tramways" network (about 42km) was for good closed in 1936. The trend reached France a few years later. Covering a peak distance of 65 km, the old tram in Valenciennes ran for the last time in 1976. Obviously, trams gradually were removed and made room for cars in the urban planning policy after the war. In both countries, the disappearance of tram networks was so massive that at the end of the 1970s, it remained only residual tram lines [START_REF] Emangard | Le contraste des politiques européennes en matière de tramways[END_REF] that had a specific reason to be not dismantled.

The renewal of French trams started in Nantes in 1985, and in Grenoble in 1987. In about thirty years, "France has almost managed to reintroduce the tram in major cities, but with reduced spatial consistencies" [START_REF] Paris | Désiré, puis haï, et enfin adulé : les tribulations du tramway dans les villes de France[END_REF]. Since 1985, only three cities maintained a part of their tramlines, but at present, twenty-four urban areas (highly variable population size) are served by a new tram-based system. This French renewal has no equivalent in the United Kingdom (Figure 1) even if most of the light rail systems in England serve urban and suburban regions while the French tram lines are shorter and serve areas within the city itself. Only five modern trams opened in the United Kingdom (London, Birmingham, Manchester, Sheffield and Nottingham), essentially during the 1990s. In 12 years, only the Nottingham Express Transit (NET) was introduced versus fourteen tramways in France (including Valenciennes one). How can we explain such differences between the British shy comeback and the French major renewal? Comparing decision-making processes in these countries draw up a few answers.

Two national decision-making models

Relating to the national context, the government strategy of each country is based on the principle of sustainable development. In the UK, the publications of the "Transport Ten Year Plan" (2000), the White Paper "The Future of Transport : A Network for 2030" (2004) and other documents, recognise the need to build a transport system that underpins long-term economic growth and productivity. In France, the «Grenelle» laws (2009)(2010) were designed to take long-term decisions on sustainable development and to support the improvement of public transport.

Concerning the local context, urban transport policies are organized by the local government : Unitary authority in England and local authority in charge of urban transport in France. The main tool for local transport planning is respectively the Local Transport Plans (LTPs) and the "Plan de Déplacement urbain" (PDU). Beyond these similarities, [START_REF] Hylén | Making tracks-Light rail in England and France[END_REF] underlines the main differences between urban transport policies in these two countries : in England, the bus transport system is unregulated and the most part of the public transport market is outside of government planning while the french situation is the other way round . Indeed, we can talk about a strong French local government with local resources of public transport funding. Conversely, in England, the local government initiatives are limited because of few financial freedom and mostly depend on a financial assistance from the central government On the one hand, this transport political context influences the decision-making process and, on the other hand have an impact on the various constraints for the development of tram project. In the United Kingdom, we can note a well-centralized decision-making process based on an economic reasoning. As tram projects funding mainly depends on central government's subsidies, local authorities may have some difficulties to implement such projects by their own resources. Even if the funding does not completely rely on governmental subsidies, financial ressources, provided by local authorities are very limited 3. Since 1968, Section 56 of the "Transport Act" defines the method to obtain subsidies from the government. According to the cost-benefit analysis, the cost of a public service concession has to be covered by non-users benefits (e.g. reduction of road congestion and pollutant emissions, saving time, reduction of car accidents). All these benefits are highly dependent on assumptions such as time or life values that are difficult to measure. Since the implementation of a new assessment method in 1998 (called the "New Approach To Appraisal NATA") by the Ministry of Transport, several tram projects (Liverpool, Leeds, London, Bristol and Portsmouth) that would have had many social advantages had been rejected [START_REF] Mackett | The impact of new urban public transport systems: will the expectations be met ?[END_REF].

In France, the situation is different because it refers to a decentralized model based on political enthusiasm. We can say that local public transport policies have in general the means of achieving their ambitions. With the successive laws related to the decentralization (since 1982), French local authorities whose do not have yet a tramway, have technical and financial means, such as the possibility to increase the transport tax4 when a public authority commits to implementing a tram project. This mode is really appreciated in local policies depending on the leader role of a powerful mayor [START_REF] Offner | Le tramway Saint-Denis-Bobigny entre enjeux et usages la décision à l'épreuve du territoire[END_REF][START_REF] Hamman | Le tramway dans la ville. Le projet urbain négocié à l'aune des déplacements[END_REF]. The French assessment model of tram projects is often reduced to get a validation of political choices [START_REF] Richer | Des tramways contre-nature ? Regards croisés sur les processus de décision des projets de TCSP de l'arc Sud de l'aire métropolitaine lilloise[END_REF]. This process is quite an efficient tool: almost all urban areas of more than 200,000 inhabitants in France have one or several modern tramways. Over and above the local political support, the role of the State in these countries also differentiates the decision-making process. The French Ministry of Transport has a more incentive role (by legislating, by giving financial means) rather than a coercive role (regarding assessment for example). The national policy about the Grenelle of Environment clearly states that it considers the tram as a flagship of sustainable development policies. Such differences may result from different social and political cultures, but also from contrasts of public transport aims [START_REF] Hylén | Making tracks-Light rail in England and France[END_REF]. In the United Kingdom, the challenge is to reduce car traffic congestion by implementing a more efficient mode of transport with limiting public spending; though in France, the objective is more to develop a sustainable city with stakes about intermodal transport practices in multilevel public policies. However, we have to keep in mind that every boundary is permeable and that other national, regional or local contexts may lead to complex adaptation of these models. These hypotheses will be compared to more practical cases.

2/ Tram comeback in Nottingham and Valenciennes conurbations Geographic and institutional context

Nottingham is the 20 th city of the United Kingdom (300 000 inhabitants) located in a metropolitan urban area which is approximately 666,000 inhabitants within a radius of 15 km around the central town (about 700 km²).

Valenciennes is a small central town of 45,000 inhabitants (15 km²) in an urban area of 400,000 inhabitants (757 km²). It is the 26th largest urban areas in France. Nottingham's urban area is characterized by a higher level of population and a higher density (approximately 1000 inhab/km² versus 550). In spite of this disparity, those two conurbations can be seen as intermediate cities in both countries cities ranking (Figure 2). Besides, they have quite similar characteristics. In fact, both urban contexts are inherited from the industrial era in these coal-mining regions. Their industrial history has left many physical (brownfield), social (high rate of unemployment) and demographic stigmas (significant population decline until 2000).

FIGURE 2. General situation of case studies

Regarding to the institutional organization, both conurbations have different functioning. In Valenciennes, local competencies (urban planning, housing, roads, parking) are shared between two recent intercommunities (created in 2000)5 but for transport policy, they transferred their competence to a same local transport authority (SITURV, acronym for "Syndicat Intercommunal des Transports de la Région de Valenciennes"). SITURV manages Local Transport Plan called "Plan de Déplacement Urbain"(PDU) and the urban public transport network called Transvilles that serves 82 municipalities located in the urban area. In Nottingham, the city is an unitary authority since 1998 and has larger local competencies in public services. The County of Nottinghamshire, an important political subdivision in the United Kingdom with a local government, handles Nottingham in an independent manner. Although it is a non-metropolitan County, the Council of Nottinghamshire obtained a transport competency in 1974. The Nottingham City Council and the Nottingham County Council became the tram project promoters. By composing the Local Transport Plan for Greater Nottingham, a document that plans transport policies for five years, both authorities guaranteed that the tram project would achieve the objectives set up.

Genesis of tram projects

Like most European cities, buses gradually replaced the old tramway in Nottingham and Valenciennes cities. But the bus system quickly revealed its limits facing the automobile development. Typically, it is in a context of a public transport crisis and an increasing road congestion that local authorities question for best solutions to resolve these difficulties. In both cities, modern tramway projects were initiated by local actors, more precisely by an association of public and private stakeholders in Nottingham, and by public actors driven by the transport authority and its operator in Valenciennes. Though the cars traffic growth is seen as a major problem in both countries, they do not share the same conception of the risk. Indeed, local authorities in Nottingham are really worried by cars threat to the economic situation, while authorities in Valenciennes are rather worried by the public transport network efficiency.

In the British city, the city and the County decided to collaborate with private stakeholders (controlled by the NDE -Nottingham Development Enterprise in 1987) in order to carry out a feasibility study about an evaluation of the best mode of transport in this case. A tram-train system using one of the old "Robin Hood" railway tracks was studied and dropped for security reasons and excessive costs. In Valenciennes, even though the President of SITURV (Jules Chevalier) was convinced of the usefulness of a modern tramway, one study (INRETS, 1991) concluded that Valenciennes could have a structuring Public Transport system. Several rolling stocks were considered and the best solution seemed to be the tram. The project called "Transvilles" targeted the reorganization of public transport network in the urban area of Valenciennes by implementing a modern trambased system and by a redeployment of bus lines.

Although politicians already decided these two tram projects in the early 1990s, the start of works did not occur until the early 2000s (from 2001[START_REF] Hass-Klau C | Economic impact of light rail: the results of fifteen urban areas in France, Germany, UK and North America[END_REF]in Nottingham, and from 2003to 2006 in Valenciennes). Why did it take a decade to set off their implementation? The temporality of the decision-making process is quite similar in the two cities but the reasons for their length of time are different: a British complexity due to the setting up of an innovative public private partnership versus an important weight of local political negotiations with mayors in France [START_REF] Frère | Structuration intercommunale et rôle des politiques de transports publics dans le Valenciennois[END_REF]. After a long decision-making process, the success of Nottingham's tram project seems to be the consequence of the choice of original governance based on a strong involvement of public sector and a partnership with economic actors through the Greater Nottingham Light Rapid Transit (GNRLT). In the 1990s, the only way to progress would be to raise funding through a Private Finance Initiative (PFI). That is to say the main financial risk would have been borne by private sector (i.e. the Arrow Consortium). In the end, the final green light for the project was given on 3 April 2000, some 8 and a half years since the original Bill was submitted to Parliament 6 . In France, difficulties in trams implementation seem to be more related to political aspects. Each municipality (5 municipalities were concerned in the first phase of implementation, 4 for the second phase concerning Denain) had to approve the tram route on its municipal perimeter and this approbation could take time such as the city of Valenciennes who was the last city that approved the route after more than one year of bargaining. As compared to the national model, Valenciennes tram project followed the same practices regarding the project packaging and its legitimisation. The only difference is the time spent in local political negotiations that could have been reduced with more cohesion in the political support.

The NET was the first UK light rail system to be wholly implemented under the Government's Private Finance Initiative. The first line opened on 9 March 2004, cost 250 million euros to implement (about 17 million euros per km). Compared to the systems currently in operation in the UK, as highlighted in the National Audit Office report ( 2004), the NET is slightly more expensive than the average cost of a light rail scheme (approx 14 million euros per km). However, it is less expensive than the average cost of a French tram (approx 25 million euros per km) because in England, urban regeneration costs are not included in the overall figure. In Valenciennes, the first tram line cost is 340 million euros (19 million euros per km). But there are strong differences between the first phase implemented in the urban area (28 million euros per km, opened in 2006) and the second phase in an interurban section (8 millions euros per km, opened in 2007). For the first phase of implementation, the increase of the local transport tax in 1997 provided a "self-financing" of about 90 M€ while the government had awarded a grant of 42 million euros.

Trams with two territorial facets

Tramway spatial characteristics are the reflections of project goals and could be considered as a result of the way to express powers. The two tram systems are entirely based on new railway infrastructures, respectively on 14 km (24 stations) for Nottingham and 18 km (28 stations) for Valenciennes. Both trams have similar technical characteristics (Nottingham has 15 Incentro trains built by Bombardier; Valenciennes has 21 Citadis trains built by Alstom), but the French tram has a more sophisticated design (Figure 3). Based on a tramway system which links two major cities, the several facets along the route give us the impression of a tram-train system even if we can note a traditional urban section with short distance between two stations (about 500 meters) and a rather modest commercial speed (less than 20km/hour) on a railway platform which is opened and integrated in the road network.

FIGURE 3. Picture of tram rolling stock near city center

After 5 km through the centre of Nottingham, the tram line is inserted along the "East Midlands" railways (Robin Hoot Line) from Wilkinson Street to Hucknall (9 km). On this section, the tram can be considered as a "light rail" with an insertion principle like a railway track (ballasted and closed platform), long distance between two stations (900 m even 1,6 km between Moor Bridge and Butler's Hill) that allow higher commercial speed (39 km/h on this section, with a peak speed of 80km/h). The aim was to provide very competitive travel time and to minimize the platform insertion costs by implementing a single track on nearly 5 km. In Valenciennes, long distance between two stations in the suburban section between Valenciennes and Denain characterize the first line as it goes through unbuilt areas (3 stations on a 6 km distance). By reusing former railway corridors that belonged to the Anzin Mining Company, the tram is like an interurban transport system with a commercial speed close to 35 km/h. In both cities, transport authorities decided to adopt a tram-train function. Why has the conventional railway network not been fully enhanced? In Nottingham, we can say that the relation between the tram and the conventional rail network consists in cohabitation between two networks (it might even be considered as a competition between Hucknall, Bulwell and the Nottingham station). In Valenciennes, we can talk about indifference, as there is no connection between tram and train. Both cities wanted to support the tram legitimisation by avoiding any mix up with the traditional railway system. In England, the commercial service's visibility was targeted, whereas in France, an institutional visibility was rather aimed. In fact, the French tram could be considered as a showcase of the local authority that supported this project. In spite of these common aspects, both models differ from their networks urban insertion. As any classic French tramway, the French line is well integrated in the landscape with an opened track covered with grass. Furthermore, the tram platform is separated from the road network but shared with pedestrians. However the situation is different in Nottingham because the tram platform is shared with car traffic (Figure 4). The French tramway is part of the urban public transport network and put together with the bus network. In England, road public transport is unregulated and the connection between bus and tram is considered on a case by case basis. However, when local bus companies have a significant role in the light rail operating consortium, such as Nottingham City Transport, the integration is better conceived. the success 7 of the NET is presented as a consequence of its integration with other transport modes. Indeed its integration had been thought with the heavy rail services via the tram terminus at Nottingham Station, the provision of over 3,000 Park and Ride spaces along the route and the operation of frequent circular bus services in the north of the City as a feeder for the tram. Finally, we can denounce the weakness of a policy to limit car uses (roads and parking). In both cities, the tram implementation seems to go along with plenteous compensations regarding cars in a competitive or a complementary manner [START_REF] Frenay | Le Tram, outil en faveur d'une ville durable ?[END_REF].

3/ Tramway and urban renewal : similarities and differences between Denain and Hucknall Presentation of Denain and Hucknall

At both tramway terminus, Hucknall (30,000 inhabitants) and Denain (20,000 inhabitants) can be considered as two interesting examples to compare urban mutations subsequently to the tram opening. These two cities are in similar situations: old mining town, demographic decline, high unemployment rate … Hucknall (since 2004) and Denain (since 2007) are served by modern tram (frequency is about 10 minutes and time to reach the city centre is about 30 minutes). The mutations approach relies on visits of the network, on a spatial analysis based on aerial photographs taken at different steps of the tramway implementation, and studies of several transport planning. The aim is to analyse urban transformations as a result of the tram implementation in a qualitative way.

The tram and public spaces quality

Qualitatively speaking, the tram's arrival played very different roles in Hucknall and Denain. At the Nottingham Express Transit terminus, as along the 9 km tracks going along the railway, the tram integration in the urban landscape is very superficial with ballast tracks as it is on the conventional railway infrastructures. The tram station and the railway terminal station are put side by side, and can even be mixed up. The railway terminal station has no station building and there is no "signal" and no square in front of the tram station that would announce the new modern tramway. More generally, the quality of surrounding public places did not change after the tram's arrival. The only transformation would be a pavement going to the town-centre by crossing the huge parking near Hucknall station. The city's masterplan (2009) gives priority to the layout of a finer connection between the town-centre and the tram station. To conclude, the tram project integration in public space has been shy and nowadays local authorities have to make efforts in order to fit the tram in the city.

In Denain, the impression is totally different because along the tram, the tracks have been extremely neatly integrated in the landscape. The tram enters the city of Denain by using an old railway corridor. Nevertheless, its route does not stop at the end of the railway corridor but is extended in the main shopping street (Villars Street). The tram implementation was the opportunity of a complete renovation of the concerned streets and roads. It included the perimeter defined by the built fronts but also the underground networks and any aerial equipment (any street furniture, plants, lightning...) [START_REF] Frenay | Le Tram, outil en faveur d'une ville durable ?[END_REF]. In a very French style 8 , it led to a deep renovation of surrounding public space. It is seen like an "urban planning tool" in order to rethink the city. As evidenced by the intermodal hub located at Villars Place, at the terminus station that is covered by a huge glass ceiling and decorated with an impressive architectural signal. Qualitatively speaking, the "introverted" Hucknall tram and the "extroverted" Denain tram are opposed (Figure 5). than ten million passengers per year (NET has exceeded the most optimistic predictions) and has contributed to a 20% uplift in public transport use at peak times from the northwest corridor into the city. 8 "In France, all new systems also involve improvements of the cross streets with the laying of new road and pavement surfaces and new street furniture and the cleaning of the fronts of buildings. The overall effect is to provide a significant facelift along the route to match the modern vehicles being introduced, although at an additional cost" (NAO, 2004). The tram and urban projects' intensity Quantitatively speaking, the observation of urban transformations is based on the analysis of aerial photographs taken at three stages (two or three years before the tram line's opening; at the tram line's opening; three or four years after the tram's implementation). Before the tram (in 2001 in Hucknall and 2005 in Denain), both cities were characterised by an important real estate potential coming from brownfield areas and other railway ones. These several and well located plots could be the support of urban planning policy.. In Hucknall, the west close areas of the NET terminus were fallow lands (except a parking of about a 100 car parks). In Denain, the available real estate for further urban renewal is also significant. However, the parcels seem to be hardly transformed because the aged industrial buildings and their pollution or contaminants have not been removed. At the tramway opening in both cities (in 2004 in Hucknall and2007 in Denain), we can note some different urban changes. In Hucknall, despite layouts for the transport service (transformation of the parking area in front of the railway station into a Park-and-ride with a capacity of 450 car places), plots next the tram station will rapidly support new urban projects. Near the city-centre, the Ashgate area is quickly urbanized: a new road connecting the North to the South is opened, a Tesco supermarket is built in front of the Park-and-ride and next to the tram station, and new residential areas are engaged (under construction, but some of them were completed). In Denain, the noticeable layouts at the tram opening were essentially made in a qualitative manner as explained before. Except road and tram stations works, there is not even the beginning of the implementation of an urban intensification around the tram in 2007.

Three years after the tram opening, the enhancement of real estate opportunities is quite different in Hucknall and Denain. At the NET terminus, housing estates have been built at less than 500 meters away from the tram station. There are various types of housings and they mainly target the upper middle class. Most plots are urbanised or will soon be. The tramway proximity is promoted in the promoter's advertising leaflets :« believe in an easy commute » is the advert written by estate agencies and pasted in the tram. In 2007, the urban planning project of the Papplewick Lane area (located in the East of the station) was initiated in spite of high tensions concerning the residential area development on green spaces and agricultural parcels (adopted on March 2004). At the end, Hucknall has 3,000 more housings than before the tram. Despite the green belt, the studies confirm that "some residential and employment growth in this area is suitable and desirable, and should support the role of Hucknall as a sub-regional centre" (tribal urban studio). At Valenciennes tramway terminus, the development seems to be slower with some desynchronization with the tram project. In 2010, some evolutions can be noted with the first works relating to new shops on the activities area of "Nouveau Monde" (Figure 6).

The first residential developments occurred in 2011 and have been strengthened since this date because we can see in 2013 that the two side areas are fully urbanized. Urban changes around these two tram terminus have been occurred at different time scales. Are they the image of a more spontaneous anticipation effort in Hucknall? The analysis of the tram project genesis in Valenciennes shows that this project, from its upstream thinking (early 2000s), had to adapt itself to the urban plan projects and especially to the urban renewal project for the "Nouveau Monde" area in Denain. The initial political wish, based on the idea that the tramway may be an accompanying tool of the important renewal project on this fallow land area, did not happen in terms of time.

Instead, the tram got ahead so that in September 2007, during the tram opening inauguration, the mayor of Denain considered this tram as an opportunity to make "a major boost" to all projects in the urban renewal programs. This discourse shows a change in the strategic point of view of a tramway. Indeed, from now on, the tramway is seen as a leading role in the implementation of urban projects. This change may be the result of a complex governance required for the maturation of urban projects which were yet planned when the tramway project was under discussion. FIGURE 6. A map of the urban projects supported in Denain and Hucknall

Tramway and urbanism: modest links?

In Hucknall, gentrification is widely promoted, in order to stabilize real estate prices at a satisfactory level and to attract wealthier families. In France, this strategy is quite feared. In Valenciennes, actors rather prefer to provide housing for social classes through their urban densification policies. In both Hucknall and Denain, the implementation of commercial areas in the suburbs and near tram stations leads to doubt about a phenomenon of real estate costs' increase. In Hucknall, a pet shop was set up on the last land adjacent to the Park-and-ride and it turns its back to the tramway. In Denain, different shops were built just close to the tram but they rather seem to be a way to implement a new commercial area than to seize the opportunity offered by the tram to set up proximity stores. In both cases, the added value of these new commercial activities seems to be weak for the tramway. We may even say that, without the tram, the urban dynamics of both municipalities would have been the same.

Finally, in Hucknall and in Denain, the tram urban planning seems to be representative of both national models. In Nottingham, the tram improved the accessibility of more than 70 recent building projects and also future ones. More precisely, it seems that the policy of land anticipation urged on the tram's implementation on this axis. In Denain, we have the opposite situation. The tram got ahead urban projects for political reasons (balance of investments between two communities, agreements on projects) and social reasons (need to change the city image). As a result, the current challenge is to implement new urban projects around the tram by an ambitious urban planning process.

Conclusion: to a cross-fertilisation of models?

This paper points out the differences between the English tramway of Nottingham and the French one in Valenciennes. At the national scale, decision-making processes in these two countries follow different logics. For the British case, the decision comes under the national level, and local tram projects must comply with a long and complex social and economic assessment process. For the French case, the decision relies on local authorities that have financial levers, while the government appears to be rather an accompanying partner than a control role. Putting two theses projects into perspective, we can work out in detail these contrasting models. In Nottingham, the tram project was completed thanks to a successful public-private partnership packaging, while in Valenciennes, the process had to achieve political negotiations with every mayor involved. Both trams also differ regarding their urban integration. The landscape quality is not the same in the two cities, especially when we compare the tram's specific role in public spaces at the terminus stations. Such differences tend to prove that an infrastructure with same characteristic can be conceived, implemented and governed in different ways. Consequently, local authorities can seize differently territorial opportunities given by the project.

But nowadays, in these two countries, one can observe continuity in the tramway enthusiasm. Thus, the Tramlink Nottingham consortium obtained in 2011 the contract to implement and operate the two new tramlines to Chilwell (10 km, to the West of the central station) and to Clifton (7.5 km, to the South of the central station). The Nottingham tramway network will expand by more than the double until the end of 2014. In Valenciennes, the second line that will connect Valenciennes to 25 stations) will open at the end of 2013. With more than 30 km tracks in a few years, those two conurbations may be classified among the major European cities served by a modern tramway.

To conclude, these new implementations show that there is some kind of hybridisation of French and English models. The tram expansion project in Nottingham seems to be "frenchified" (infrastructure, rolling stock, new local resource of public transport funding9 ). Firstly, the presence of French companies (Alstom, Kéolis, Vinci)who are involved in French tram implementation -in the Tramlink Nottingham consortium will have some influence. Then, the community reaffirms its commitment to set up a whole multimodal network with a single operator for all the tramlines that will be complementary to buses. Finally, one can discover a new kind of argument for the tram: the image of Nottingham city that is widely used in France. In France, the current debate focuses on issues about costs control and land effects. In Valenciennes, the new line under construction is different from the first one because of its controlled cost (approximately 10 million euros per km) thanks to a single track that is less implemented in France than in the United Kingdom. Finally "more beautiful "and "less expensive" are a shared model, but a challenge to implement.

FIGURE 1 .

 1 FIGURE 1. Map of trams in France and in the United Kingdom

FIGURE 4 .

 4 FIGURE 4. A tram route in Nottingham and Valenciennes

FIGURE 5 .

 5 FIGURE 5. Terminal station in Hucknall and Denain

FIGURE 7 .

 7 FIGURE 7. View of new urban development around the tram

A local tax on car parking can be introduced by a County or an Unitary Authority to finance improvements of the transport system

The "Versement Transport" is a local tax paid by firms with more than 9 employees in order to fund urban public transport. Its basic rate is 1% of payroll costs. It can be raised to 1,80% when public transport authorities want to implement a first tram-based system line.

The "Communauté d'agglomération de la porte du Hainaut" (CAPH) in the West and the "Communauté d'agglomération de Valenciennes Métropole" (CAVM) in the East, are administrative structures that consist in a partnership between different municipalities in order to initiate integrated urban development plans.

Nottingham Express Transit: The Background to the Project. Article Posted Sunday

March 2004 http://www.britishtramsonline.co.uk/netbackground.html

After six years of operating(2004)(2005)(2006)(2007)(2008)(2009)(2010), the Nottingham Express Transit (NET) has obtained a 92% satisfaction rate, is used by more

Based on the model of the "versement transport" tax, Nottingham City Council is developing a "Workplace Parking Levy" (WPL) scheme to invest on some local transport improvements (future extensions to the Nottingham Express Transit). The WPL is a charge on employers that provide workplace parking. The money raised from Nottingham's WPL increases financial freedom of local government.


Thomas Nowak
email: nowak@lix.polytechnique.fr

Bernadette Charron-Bost

An Overview of Transience Bounds in Max-Plus Algebra

Keywords: 2010 Mathematics Subject Classification. Primary 15A80; Secondary 05C20, 05C22, 05C50

We survey and discuss upper bounds on the length of the transient phase of max-plus linear systems and sequences of max-plus matrix powers. In particular, we explain how to extend a result by Nachtigall to yield a new approach for proving such bounds and we state an asymptotic tightness result by using an example given by Hartmann and Arguelles.

Introduction

Max-plus linear algebra is used to describe production and transportation systems, and several distributed algorithms, due to the occurrence of a temporal maximum operation when events are synchronized. These systems are described by the repeated application of a fixed matrix to an initial vector. A body of research spawned examining the behavior and parameters of interest of max-plus linear systems. If the system matrix is irreducible, i.e., if the digraph described by it is strongly connected, one observes a periodic behavior after an initial transient phase whose length we refer to as the transient: If x(k) denotes the system vector after k applications, then x i (k + p) = x i (k) + c with a constant c independent of index i for all k large enough, i.e., greater or equal to the transient. This was first shown by Cohen et al. [START_REF] Cohen | Analyse du comportement périodique de systèmes de production par la théorie des dioïdes[END_REF]. In fact, they showed that the entries in the sequence of max-plus powers A ⊗k of every irreducible matrix A are eventually periodic in the same sense, i.e., A ⊗(k+p) i,j = A ⊗k i,j + c with some c independent of the index (i, j) for all k large enough. This obviously implies the result for systems. In the same vein, the transient of a system is always upper bounded by the transient of the sequence of powers of its system matrix.

It is the purpose of this paper to survey the existing upper bounds on the transient of max-plus linear systems and matrices. Preceding the first general transience bound by Hartmann and Arguelles [START_REF] Hartmann | Transience bounds for long walks[END_REF], a number of upper bounds on the transient of certain max-plus linear systems in computer science were established (e.g., [START_REF] Even | The use of a synchronizer yields the maximum computation rate in distributed networks[END_REF][START_REF] Malka | Analysis of distributed algorithms based on recurrence relations[END_REF][START_REF] Charron-Bost | Full reversal routing as a linear dynamical system[END_REF][START_REF] Chrétienne | Chemins extrémaux d'un graphe doublement valué[END_REF]). All these results are, as far as we are aware of them, covered by the bounds we chose to present here.

Hartmann and Arguelles [START_REF] Hartmann | Transience bounds for long walks[END_REF] proved, as a corollary of their upper bound on the transient, that the computation of the exact value of the transient of a system or a matrix can be done in time polynomial in the size of a list representation. Their algorithm first calculates an upper bound on the transient and then identifies the transient by doing a binary search. Consequently, better upper bounds improve the running time of this algorithm. Also, bounds involving certain parameters of the systems or the matrix allow to design for a small transient.

The paper is structured as follows: Section 2 defines the basic notions used in the paper and presents some preliminary results used later. Section 3 discusses selected upper bounds on the transient for the special case of Boolean matrices. In Section 4, we present the decomposition of the sequence of matrix powers as a maximum of matrices with bounded transients established by Nachtigall [START_REF] Nachtigall | Powers of matrices over an extremal algebra with applications to periodic graphs[END_REF]. We also explain how his arguments can be extended and completed to show a bound on the transient of the sequence of powers. This extension was presented by the authors at the workshop TROPICAL-12 [START_REF] Charron-Bost | General transience bounds in tropical linear algebra via Nachtigall decomposition[END_REF]. Section 5 gives the first general transience bound proved by Hartmann and Arguelles [START_REF] Hartmann | Transience bounds for long walks[END_REF]. It also includes the generalization of one of their examples showing a form of asymptotic tightness of their bound, and also of other bounds. In Section 6, we present a bound for a special class of max-plus matrices that was proved with a technique used by Akian et al. [START_REF] Akian | Discrete max-plus spectral theory, Idempotent Mathematics and Mathematical Physics[END_REF] and Bouillard and Gaujal [START_REF] Bouillard | Coupling time of a (max,plus) matrix[END_REF]. Section 7 gives the bound by Soto y Koelemeijer [START_REF] Soto Y Koelemeijer | On the behaviour of classes of min-max-plus systems[END_REF] for the special case of max-plus matrices whose all entries are finite. Section 8 presents the bounds by Charron-Bost et al. [START_REF] Charron-Bost | New transience bounds for long walks[END_REF] that use two graph parameters (girth and cyclicity). In Section 9, we present the method by Charron-Bost et al. to transform transience bounds for systems into transience bounds for matrices. With Section 10, we conclude the paper by comparing the bounds from both a quantitative and a qualitative viewpoint.

Definitions and Preliminaries

In max-plus algebra, one endows the set R max = R ∪ {-∞} with the addition a ⊕ b = max{a, b} and the multiplication a ⊗ b = a + b. The identity with respect to ⊕ is -∞ and 0 with respect to ⊗.

A max-plus matrix is a matrix with entries in R max . The max-plus product of two matrices A and B of compatible size is defined in the usual way by setting (A ⊗ B) i,j = h A i,h ⊗ B h,j . We write A ⊗k for the kth max-plus power of a square matrix A.

A digraph is a pair G = (V, E) of a nonempty set V of nodes and a set E ⊆ V ×V of edges. A walk in the digraph is a path if every node occurs only once. A closed walk is a cycle if only the start and end node occurs twice. We write ℓ(W ) for the length of walk W .

The length of the shortest cycle in a digraph G is called the girth of G. If a digraph is strongly connected, the greatest common divisor of its cycle lengths is called its cyclicity. The cyclicity of a (possibly not strongly connected) digraph is the least common multiple of the cyclicities of its strongly connected components.

To every n × n max-plus matrix A corresponds a digraph G(A) with node set V = {1, 2, . . . , n} containing an edge (i, j) if and only if A i,j = -∞. We refer to A i,j as the weight of edge (i, j). Matrix A is irreducible if G(A) is strongly connected. If W is a walk in G(A), we define its weight A(W ) as the sum of the weights of its edges. The entry A ⊗k i,j is the maximum weight of walks from i to j of length k. 1 If v is a max-plus column vector of size n, then the entry A ⊗k ⊗ v i is the maximum of the values A(W ) + v j where the maximum is formed over all nodes j and all walks W from i to j of length k.

Denote by λ(A) the maximum mean weight A(Γ)/ℓ(Γ) of cycles in G(A). We call critical every cycle with maximum mean weight. The subgraph of G(A) induced by edges on critical cycles is called the critical subgraph.

Let X be a fixed index set. A sequence a : N → R X max is called eventually periodic with period p ≥ 1 and ratio ̺ ∈ R if there exists a K ∈ N such that a(k + p) = a(k) + p • ̺ for all k ≥ K, where the addition is to be understood component-wise. The smallest such K is the transient of the sequence. The ratio is unique if not all components of a(k) are eventually constant -∞. For every eventual periodicity of sequence a(k) with ratio ̺, the sequence a(k) -k • ̺ is eventually periodic with ratio 0.

The following lemma shows that the transient is independent of the considered period. For a proof see, for instance, [START_REF] Hartmann | Transience bounds for long walks[END_REF]Lemma 11].

Lemma 2.1. Let a(k) be a sequence, p, q positive integers, K p , K q nonnegative integers, and ̺ a real number. If a(k

+ p) = a(k) + p • ̺ for all k ≥ K p and a(k + q) = a(k) + q • ̺ for all k ≥ K q , then a(k + gcd(p, q)) = a(k) + gcd(p, q) • ̺ for all k ≥ max{K p , K q }.
Cohen et al. [START_REF] Cohen | Analyse du comportement périodique de systèmes de production par la théorie des dioïdes[END_REF] showed that the sequence of powers of an irreducible max-plus matrix, and hence of all systems with irreducible matrix, are eventually periodic. Denote by γ c (A) the cyclicity of the critical subgraph of G(A).

Theorem 2.2 [START_REF] Cohen | Analyse du comportement périodique de systèmes de production par la théorie des dioïdes[END_REF]. The sequence of powers A ⊗k of an irreducible square max-plus matrix A is eventually periodic with ratio λ(A) and period γ c (A). Theorem 2.2 is based on the fact that maximum weight walk eventually include in the majority critical cycles. To give an explicit upper bound on when they visit at least one critical cycle, several authors defined what they considered to be the "second most significant" cycle mean. This can be done in a number of ways, depending on the specific proof technique used: One possibility, used by the authors' extension of Nachtigall's decomposition and by Soto y Koelemeijer, is to consider the second largest cycle mean λ 2 (A). Bouillard and Gaujal and Charron-Bost et al. both considered the largest cycle mean disjoint to all critical cycles, which we denote by λ nc (A). Hartmann and Arguelles used a third parameter, λ 0 (A), which is defined in terms of the max-balancing [START_REF] Schneider | Max-balancing weighted directed graphs and matrix scaling[END_REF] of G(A). We do not formally define the three parameters, but give their relative ordering, also with respect to λ(A):

(2.1) λ(A) > λ 2 (A) ≥ λ nc (A) ≥ λ 0 (A)
We denote by A the difference between the greatest and smallest finite entry in matrix A.

The Boolean Case: Index of Convergence

A Boolean matrix is a max-plus matrix whose entries are either -∞ or 0 and it corresponds to a digraph. The behavior of the sequence of powers of Boolean matrices, or equivalently the set of possible walk lengths between nodes in a digraph, has been extensively studied (see, e.g., [START_REF] Brualdi | Combinatorial matrix theory[END_REF] or [START_REF] Li | The index set problem for Boolean (or nonnegative) matrices[END_REF] for an overview). If the digraph is strongly connected, Theorem 2.2 shows that every such sequence is eventually periodic; for the critical subgraph is equal to the whole digraph. Its transient is commonly referred to as the index of convergence of the matrix resp. the digraph (also sometimes the exponent if the cyclicity is equal to 1). Clearly, the case of Boolean matrices is an important special case for the study of transients in maxplus algebra.

The first bound on the index of convergence was given by Wielandt [START_REF] Wielandt | Unzerlegbare, nicht negative Matrizen[END_REF] for the case of primitive digraphs, i.e., digraphs whose cyclicity is equal to 1. He also gave a class of examples showing his bound is tight.

Theorem 3.1 [START_REF] Wielandt | Unzerlegbare, nicht negative Matrizen[END_REF]. The index of convergence of a strongly connected primitive digraph with n nodes is at most (n -1)2 + 1. Furthermore, for every n ≥ 2 there exists a strongly connected primitive digraph with n nodes whose index of convergence is equal to (n -1) 2 + 1.

The bound of (n -1) 2 + 1 was refined independently by Dulmage and Mendelsohn [START_REF] Dulmage | Gaps in the exponent set of primitive matrices[END_REF] and by Denardo [START_REF] Denardo | Periods of connected networks and powers of nonnegative matrices[END_REF] in terms of the digraph's girth g. They arrived at the same bound, which is in the order of O(g • n). This suggests that the lower the girth, the lower the index of convergence.

Later, Schwarz [START_REF] Schwarz | On a sharp estimation in the theory of binary relations on a finite set[END_REF] extended Theorem 3.1 to non-primitive digraphs. 2 Interestingly, he showed that the bound of (n-1) 2 +1 remains true and that even a lower upper bound holds, which in the order of O(n 2 /γ) where γ denotes the cyclicity. This suggests that the higher the cyclicity, the lower the index of convergence.

Because the girth of a strongly connected digraph is always greater or equal to the cyclicity, the two results suggest a necessary trade-off between the two parameters for attaining a small index of convergence. For instance, the two parameters need to be equal for attaining the minimal index of convergence of 0.

Kim [START_REF] Kim | An extension of the Dulmage-Mendelsohn theorem[END_REF] showed a new upper bound, which generalizes both the bounds of Dulmage, Mendelsohn, and Denardo, and Schwarz: Theorem 3.2 [START_REF] Kim | An extension of the Dulmage-Mendelsohn theorem[END_REF]. The index of convergence of a strongly connected digraph with n nodes, girth g, and cyclicity γ is at most

n + g • n γ -2 .

Nachtigall Decomposition

A significant step in the direction of a transience bound for non-Boolean matrices was done by Nachtigall [START_REF] Nachtigall | Powers of matrices over an extremal algebra with applications to periodic graphs[END_REF]. While he did not prove a bound on the transient, he showed that the sequence of matrix powers can be written as a maximum of eventually periodic sequences with bounded transients. Such a decomposition in the form of a maximum, by itself, does not yield a bound on the transient of the original sequence; it does not even imply that it is eventually periodic. As a matter of fact, Nachtigall shows the existence of such a decomposition not only for irreducible matrices, but for general square max-plus matrices, for which the sequence of powers is not necessarily eventually periodic.

The authors [START_REF] Charron-Bost | General transience bounds in tropical linear algebra via Nachtigall decomposition[END_REF] have observed that the specific structure of the Nachtigall decomposition in the case of irreducible matrices allows to deduce a transience bound. We discuss this after the description of the decomposition. Nachtigall's decomposition was also studied by Molnárová [START_REF] Molnárová | Computational complexity of Nachtigall's representation[END_REF] and Sergeev and Schneider [START_REF] Sergeev | CSR expansions and matrix powers in max algebra[END_REF].

Theorem 4.1 [START_REF] Nachtigall | Powers of matrices over an extremal algebra with applications to periodic graphs[END_REF]. Let A be an n × n max-plus matrix. Then there exist eventually periodic matrix sequences A 1 (k), A 2 (k), . . . , A n (k) with transients at most 3n 2 such that for all k ≥ 0:

A ⊗k = A 1 (k) ⊕ A 2 (k) ⊕ • • • ⊕ A n (k)
Nachtigall proved Theorem 4.1 by recursively picking a cycle Γ with maximal ratio A(Γ)/ℓ(Γ) and by partitioning the sets of walks in G(A) into the sets of walks that do and do not visit cycle Γ. Walks that do not visit Γ are walks in the subgraph of G(A) that has all edges incident to Γ removed. This subgraph is the digraph of the matrix obtained from A by setting to -∞ all rows and columns corresponding to nodes in Γ; its effective size is strictly smaller than the size of A, which enables a recursive descent. If no cycle exists in G(A) at all, then the transient of A is at most n since in this case, A ⊗k i,j = -∞ for all i, j and all k ≥ n. One can see that the sequence of the maximum weights of walks of length k from a node i to a node j that do visit cycle Γ has a transient of at most 3n 2 in the following way: Take a node h of Γ and set B = A ⊗ℓ(Γ) . As G(B) contains a self-loop with maximal ratio at node h, the sequences B ⊗k i,h and B ⊗k h,j have transients at most n -1, which implies that the sequences A ⊗k i,h and A ⊗k h,j have transients at most (n -1) • ℓ(Γ). Both have period ℓ(Γ) and ratio A(Γ)/ℓ(Γ). It is not hard to show that, in this case, their max-plus convolution

k1+k2=k A ⊗k1 i,h ⊗ A ⊗k2 h,j
has the same period and ratio, and a transient of at most 2

• (n -1) • ℓ(Γ) + ℓ(Γ) ≤ 2n 2 -n.
This convolution is equal to the sequence of maximum weights of walks of length k from i to j that visit node h. Because the ratios of these sequences, for all h in Γ, are equal to A(Γ)/ℓ(Γ) and their transients are at most 2n 2 -n, the sequence of maxima, formed over all h in Γ, has the same ratio and a transient of at most 2n 2 -n. This argument, which is essentially identical to the one given by Nachtigall, yields a bound of 2n 2 -n, improving the bound of 3n 2 in Theorem 4.1.

We would like to point out that, if the ratios differ, the transient of a maximum of eventually periodic sequences need not be bounded by the maximum of the sequences' transients (see Figure 1). It is possible that the maximum is not even eventually periodic: If a(k) and b(k) are two eventually periodic scalar sequences such that a(k)'s ratio is strictly larger than that of b(k), then the maximum c(k) = a(k) ⊕ b(k) is eventually periodic if and only if, for all k large enough, a(k) = -∞ implies b(k) = -∞. This condition is not necessary for eventual periodicity if the two ratios are equal.

Thus, Theorem 4.1 by itself, even if A is irreducible, i.e., A ⊗k is eventually periodic, does not give an upper bound on the transient of A ⊗k . However, inspection of its proof does: By construction, if the (i, j)th entry of matrix A r (k) is finite, then there exists a walk of length k in G(A) from i to j. Because G(A) is strongly connected, by the finiteness of its index of convergence (see Section 3), if k is large enough, there exists a walk of length k in G(A) from i to j that visits an arbitrary prescribed node h. This shows that, if k is large enough, then also the (i, j)th entry

k max{Ka,K b } a(k) b(k)
Figure 1. Two eventually periodic sequences with differing ratios and respective transients K a and K b of A 1 (k) is finite. 3 Hence all sequences of the form A 1 (k) ⊕ A r (k) are eventually periodic. Their ratios are all equal to λ(A) since the first cycle to be removed is a critical one. Hence the transient of the sequence

A ⊗k = A 1 (k) ⊕ A 2 (k) ⊕ • • • ⊕ A n (k) is bounded by the maximum transient of the A 1 (k) ⊕ A r (k)'s.
By elementary calculations, one can show the following lemma which provides a bound on the transient of the maximum of two eventually periodic sequences if the maximum itself is eventually periodic. It enables us to bound the transient of This lemma enables us to deduce the following transience bound from the proof of the Nachtigall decomposition. Without loss of generality, we can assume that λ(A) = 0. When applying the lemma to A 1 (k) and A r (k), the number K is at most 2n 2 -n and p is at most n, which implies that ∆ is at most 2n 2 A . Theorem 4.3. Let A be an irreducible n × n max-plus matrix. Then the transient of the sequence of powers A ⊗k is at most

A 1 (k) ⊕ A r (k).
2n 2 + 2n 2 A λ(A) -λ 2 (A)
.

Bound by Hartmann and Arguelles

Hartmann and Arguelles [START_REF] Hartmann | Transience bounds for long walks[END_REF] gave the first general transience bound for arbitrary irreducible max-plus matrices. Their proof is purely graph-theoretic. 3 We do not need to quantify the threshold for k because eventual periodicity of A 1 (k) and Ar(k) shows that the implication is true from 2n 2n on, i.e., for all k ≥ 2n 2n, as soon as we know that it is true from some (unknown) threshold on. This suffices for our purposes.

When analyzing their proof, one can extract a global proof strategy, variants of which are also found in later proofs of transience bounds [START_REF] Soto Y Koelemeijer | On the behaviour of classes of min-max-plus systems[END_REF][START_REF] Charron-Bost | New transience bounds for long walks[END_REF]. It has been described explicitly by Charron-Bost et al. [START_REF] Charron-Bost | New transience bounds for long walks[END_REF]Section 3]. In order to prove that some number B is an upper bound on the transient of the sequence A ⊗k for an irreducible matrix A, do the following:

(1) Show that one can assume λ(A) = 0, i.e., the sequence A ⊗k is eventually periodic with ratio 0. (2) Fix two nodes i and j, and a congruence class [k 0 ] modulo some period p of the sequence A ⊗k . (3) The assumption λ = 0 guarantees that the maximum max k∈M A ⊗k i,j formed over an arbitrary nonempty set M of nonnegative integers exists. We choose the set M to consist of those elements of class [k 0 ] that are greater or equal to B. Since the maximum exists, there exists a walk W from i to j with length in M that attains it. If B is indeed an upper bound on the transient, the values A ⊗k i,j with k ∈ M will all be equal. (4) Show that, whenever the length of W is greater or equal to some "critical bound" B c ≤ B, then it necessarily shares a node with a critical cycle Γ. (5) Show that one can reduce walk W by removing subcycles such that it is possible to attain all lengths in M greater or equal to some "pumping bound" B p ≤ B by adding critical cycles. The assumption λ = 0 implies that all subcycles have weight at most 0 and critical cycles have weight equal to 0. Thus the weights of walks obtained in this way cannot be lower than that of W ; hence they are equal to that of W . ( 6 They used this lemma to reduce walk W in step [START_REF] Charron-Bost | New transience bounds for long walks[END_REF]. After their reduction their walk could be disconnected, but they showed that adding a copy of (critical) cycle Γ reestablishes connection [13, Theorem 4]: Lemma 5.2 [START_REF] Hartmann | Transience bounds for long walks[END_REF]. Let W be a walk that shares a node with some cycle Γ and let k be an integer such that k ≡ ℓ(W ) (mod ℓ(Γ)) and k ≥ n 2 where n denotes the number of nodes in the graph. Then there exists a walk W obtained from W by removing cycles and possibly adding copies of Γ such that ℓ( W ) = k.

To pump the walk length after the walk reduction, they used a result by Brauer [START_REF] Brauer | On a problem of partitions[END_REF] on the Frobenius problem to combine critical cycles to attain a multiple of γ c (A). The use of Brauer's theorem introduces a term that is necessarily quadratic in n to the transience bound. We want to note at this point that this use of Brauer's theorem can be avoided by considering a period in step (2) different from the critical subgraph's cyclicity because of Lemma 2.1. 4The same strategy as described above can be adapted to show transience bounds for systems A ⊗k ⊗ v. In the case that all entries of v are finite, it is possible to show a sharper bound because the walks under consideration do not have both the start and the end node fixed, but only the start node. This allows to circumvent the necessity of showing the existence of walks of prescribed length between two fixed nodes (see Section 3).

Theorem 5.3 [START_REF] Hartmann | Transience bounds for long walks[END_REF]. Let A be an irreducible n × n max-plus matrix. Then the transient of the sequence of powers A ⊗k is at most

max 2n 2 , 2n 2 A λ(A) -λ 0 (A)
.

If, additionally, v is a column vector of size n with only finite entries, then the transient of the system A ⊗k ⊗ v is at most

max 2n 2 , v + n A λ(A) -λ 0 (A)
.

Hartmann and Arguelles also proved a form of asymptotic tightness of their transience bound for matrices. They gave, for every n of the form n = 3m -1 and all positive reals λ and λ 0 with λ > λ 0 , an irreducible n × n max-plus matrix A with λ(A) = λ and λ 0 (A) = λ 0 (see [START_REF] Hartmann | Transience bounds for long walks[END_REF]Figure 1]). Their example has the property that λ 0 (A) = λ nc (A) = λ 2 (A) and A = λ. They showed by explicit calculation that A's transient is at least 3 + m(m -2)λ/(λ -λ 0 ). We can generalize their example to arbitrary n by inserting additional nodes that do not change the transient. This then shows that, even if one can prescribe all the other parameters in the matrix bound of Theorem 5.3, it is asymptotically tight when n tends to infinity: Theorem 5.4. Let D n and M n be two sequences of positive real numbers such that D n ≤ M n . Then there exists a sequence of irreducible n × n max-plus matrices

A n such that λ(A n ) -λ 2 (A n ) = D n , A n = M n ,

and the transient of the sequence of matrix powers

A ⊗k n is Ω n 2 A n λ(A n ) -λ 2 (A n ) .
Because λ 2 = λ nc = λ 0 in Hartmann and Arguelles' example, Theorem 5.4 also holds with either λ nc or λ 0 replacing λ 2 .

A Bound for Primitive Matrices

A certain class of graph-theoretic arguments has been developed for the case that the matrix is primitive, i.e., if its critical subgraph has a cyclicity equal to 1. 5This class of arguments was used by both Akian et al. [START_REF] Akian | Discrete max-plus spectral theory, Idempotent Mathematics and Mathematical Physics[END_REF]Remark 7.14] and Bouillard and Gaujal [START_REF] Bouillard | Coupling time of a (max,plus) matrix[END_REF]. To explicitly state a bound emerging from these arguments, we present the bound of Bouillard and Gaujal in this section. For ease of notation, we give it for the case λ(A) = 0. Theorem 6.1 [START_REF] Bouillard | Coupling time of a (max,plus) matrix[END_REF]. Let A be a primitive irreducible n × n max-plus matrix with λ(A) = 0. Then the transient of the sequence of powers A ⊗k is at most

max 2n -2 + H + (n c -2H) • ĝ , max i,j |W (nc) i,j -W (c) i,j | -λ nc (A) + (n -n c )
where n c is the number of critical nodes, H is the number of critical components, ĝ is the maximum girth of components of the critical subgraph, W

(nc) i,j
is the maximum weight of walks from i to j not visiting a critical node, and W (c) i,j is the maximum weight of walks from i to j that do visit a critical node.

Bouillard and Gaujal explained how to extend their result to the case of nonprimitive matrices: If A's critical subgraph has cyclicity γ c , then A ⊗γc is primitive. It is not necessarily irreducible, but it is guaranteed to be completely reducible, i.e., permutation similar to a blockwise diagonal matrix whose diagonal blocks are irreducible. Also, every irreducible block contains at least one critical cycle, i.e., their eigenvalues are equal, which implies that the sequence of powers is eventually periodic. If K is the transient of the sequence A ⊗kγc , then the transient of A ⊗k is at most Kγ c .

Unfortunately, the cyclicity γ c can be exponential in the size n of the matrix. This was shown by Malka et al. [START_REF] Malka | A lower bound on the period length of a distributed scheduler[END_REF]Theorem 4] who constructed matrices whose critical subgraphs are disjoint unions of cycles of prime lengths. Using the Prime Number Theorem, one sees that it is possible to construct a critical subgraph with cyclicity γ c = e Ω( √ n) . Malka et al. improved this observation by showing that even the minimal period can be in the same order: Theorem 6.2 [START_REF] Malka | A lower bound on the period length of a distributed scheduler[END_REF]. There exists a sequence of irreducible n × n max-plus matrices A n such that the minimal period of the sequence of matrix powers A ⊗k n is exp Ω( √ n) .

When All Entries Are Finite

Soto y Koelemeijer [24, Theorem 3.5.12] established a transience bound in the case that all matrix entries are finite, i.e., the corresponding digraph is the complete graph. His approach is similar to that of Hartmann and Arguelles, but the assumption of existence of all edges in the corresponding digraph allows to construct shorter walks. Utilizing this fact, he arrived at a bound that can be lower than that of Hartmann and Arguelles (first part of Theorem 5.3).

max 2n 2 , 2 A λ(A) -λ 2 (A) + n -1 .

Inclusion of Cyclicity and Girth

Charron-Bost et al. [START_REF] Charron-Bost | New transience bounds for long walks[END_REF] gave two transience bounds for systems; one that involves the maximum girth of connected components of the critical subgraph, and one that involves the maximum cyclicity. For both, they used the general proof strategy that we detailed in Section 5. With respect to this strategy, they introduced two different methods of deleting and adding cycles in step [START_REF] Charron-Bost | New transience bounds for long walks[END_REF]. Their use is enabled by considering a period p equal to the least common multiple of all critical cycle lengths in step [START_REF] Bouillard | Coupling time of a (max,plus) matrix[END_REF].

The two methods are called the repetitive and the explorative method. Denote by h the a critical node of walk W in step [START_REF] Charron-Bost | New transience bounds for long walks[END_REF]. Depending on the strongly connected component of the critical subgraph that h lies in, they choose a positive integer d as a parameter for the walk reduction Red d,h , whose definition we present later. It has the following properties: In the repetitive method, they choose some critical cycle Γ which node h is part of and choose d = ℓ(C). For pumping the reduced walk, they add copies of Γ. Since d divides p, all lengths in the congruence class [ℓ(W )] modulo p can be reached that are greater or equal to ℓ( Ŵ ).

In the explorative method, they choose d equal to the cyclicity of h's strongly connected component in the critical subgraph. For pumping in the explorative method, they add a closed walks in the component starting at h using the notion of index of convergence (see Section 3). Again, d divides p. Hence all lengths in the congruence class [ℓ(W )] modulo p can be reached that are greater or equal to ℓ( Ŵ ) + ind, where ind denotes the component's index of convergence.

The walk reduction Red d,h (W ) is defined as follows: Starting at W , one repeatedly removes nonempty collections of subcycles such that (a) their combined length is a multiple of d and (b) after their removal, h is still a node of the resulting walk. If there are more than one such collections, choose any. Eventually, all collections of subcycles that satisfy (a) and (b) will be empty. At this point, the walk reduction stops and returns the last walk. The resulting walk then has a structure as depicted in Figure 2: It is a sequence of paths P t connecting the start node to the end node via some cycles Γ t and the node h. By using Lemma 5.1, one sees that there can be at most d -1 cycles Γ t because otherwise they could be removed as they would satisfy (a) and (b). It follows that there are at most d + 1 paths P t . Since the paths have length at most n -1 and the cycles at most n, the upper bound of Lemma 8.1 on the reduced walk length follows. where ĝ, γ, and înd denote the greatest girth, cyclicity, and index of critical components of G(A), respectively.

From Systems to Matrices

Charron-Bost et al. [START_REF] Charron-Bost | New transience bounds for long walks[END_REF] also showed how to transform bounds for system transients into bounds for matrix transients. They used the following idea: The transient of the sequence of powers of a matrix A is equal to the maximum transient of systems A ⊗k ⊗v where v is one of the max-plus unit vectors. However all transience bounds for systems assume the vector v to have only finite entries, which is not the case for the max-plus unit vectors. So they considered "truncated" unit vectors that have their infinite entries replaced by -µ where µ is an appropriately chosen real number. They used this approach, together with graph-theoretical arguments, to show the following theorem.

Conclusion

We have presented various transience bounds and some of their proofs for both max-plus systems and matrices. Most of the proofs were heavily graph-theoretic, with the exception of Theorem 4.3, which is more algebraic and founded on the concept of convolution of sequences. Except for the bound of Theorem 4.3, which can be seen to be strictly greater than the others, there is no general ordering between pairs of bounds. This is due to the fact that all of them consider either a different set of parameters or a special case. A "good" choice of parameters is not an obvious to make. At one extreme, one could declare the transient itself as a parameter, which would lead to a trivial bound. At the other extreme, restricting oneself to only consider the matrix size n as a parameter is not tractable either. In fact, the tightness result of Theorem 5.4 shows that no upper bound only in terms of n exists. We think that the choice of parameters can only depend on the envisioned application of the respective transience bound. Because the problem of computing the exact transient is computationally feasible, parameters should be ones that can be controlled during the system design phase.

Lemma 4 . 2 .

 42 Let a(k) and b(k) be two eventually periodic scalar sequences with respective ratios ̺ a = 0 > ̺ b , transients at most K, and periods at most p such that a(k) = -∞ implies b(k) = -∞ for all k large enough. Then the maximum a(k) ⊕ b(k) is eventually periodic with transient at most K + p -1 + ∆/(̺ a -̺ b ) where ∆ is the maximum value of the form b(k) -a(l) with k, l ∈ {K, . . . , K + p -1} and a(l) = -∞.

Lemma 5 . 1 .

 51 ) We then have shown, because the choice of [k 0 ] was arbitrary, that the transient of A ⊗k i,j is at most B ≥ max{B c , B p }. Hartmann and Arguelles used p = γ c (A) in step (2). For step (5), they described a walk reduction based on the following basic application of the pigeonhole principle: Let d be a positive integer. Every collection of at least d integers has a nonempty subcollection whose sum is divisible by d.

Theorem 7 . 1 (

 71 Soto y Koelemeijer, 2003). Let A be an n × n max-plus matrix with only finite entries. Then the transient of the sequence of powers A ⊗k is at most

Figure 2 .

 2 Figure 2. Structure of the reduced walk Ŵ = Red d,h (W )

Lemma 8 . 1 (

 81 Charron-Bost et al., 2012). Let W be a walk containing node h and let d be a positive integer. Then there exists a walk Ŵ = Red d,h (W ) obtained from W by removing subcycles such that (i) W still contains node h, (ii)ℓ( W ) = ℓ(W ) (mod d), and (iii) ℓ( Ŵ ) ≤ 2 • d • (n -1) + d -1,where n denotes the number of nodes in the digraph.

Theorem 8 . 2 (

 82 Charron-Bost et al., 2012). Let A be an irreducible n × n maxplus matrix and let v be a column vector of size n with only finite entries. Then the transient of the system A ⊗k ⊗ v is less or equal to bothmax 2ĝ • (n -1) + ĝ -1 , v + (n -1) A λ(A) -λ nc (A)andmax înd + 2γ • (n -1) + γ -1 , v + (n -1) A λ(A) -λ nc (A) ,

Theorem 9 . 1 (

 91 Charron-Bost et al., 2012). Let A be an irreducible n × n maxplus matrix and let B be a nonnegative integer. SetB = 2n -3 + înd + ind G(A) + γwhere ind G(A) denotes the index of convergence of G(A), and înd and γ denote the greatest index and cyclicity of strongly connected components of the critical subgraph.If B is an upper bound on all transients of systems A ⊗k ⊗ v with v ≤ B • A , then the transient of the sequence of matrix powers A ⊗k is at most max{B, B}.

We follow the convention that max ∅ = -∞.

Shao and Li [23] gave an alternative proof.

Hartmann and Arguelles actually prove Lemma 2.1 later in the paper [13, Lemma 11], but do not use it in the proof of their transience bound.

This definition is consistent with the definition of primitivity for Boolean matrices (Section 3) because all cycles are critical in the Boolean case.

Acknowledgments

The authors would like to thank Marianne Akian and Anne Bouillard.


Bernadette Charron-Bost

Thomas Nowak

General Transience Bounds in Tropical Linear Algebra via Nachtigall Decomposition

We present general transience bounds in tropical linear algebra based on Nachtigall's matrix decomposition. Our approach is also applicable to reducible matrices. The core technical novelty are general bounds on the transient of the maximum of two eventually periodic sequences. Our proof is algebraic in nature, in contrast to the existing purely graph-theoretic approaches.

Introduction

Tropical linear systems describe the behavior of transportation systems, manufacturing plants, network synchronizers, as well as certain distributed algorithms for resource allocation and routing. It is known that the sequence of tropical matrix powers, and hence every linear system, becomes periodic after an initial transient. In applications it is of interest to have upper bounds on the transient, to which we contribute with this work.

We use the Nachtigall decomposition [START_REF] Nachtigall | Powers of matrices over an extremal algebra with applications to periodic graphs[END_REF] of square matrices in tropical algebra to show new transience bounds for sequences of matrix powers. The Nachtigall decomposition is a representation of the sequence of matrix powers of a square matrix as a maximum of a bounded number of sequences of bounded transients and bounded periods. Transience bounds for the sequence of matrix powers have been given, amongst others, by Hartmann and Arguelles [START_REF] Hartmann | Transience bounds for long walks[END_REF] and Charron-Bost et al. [START_REF] Charron-Bost | On the transience of linear max-plus dynamical systems[END_REF]. Their proofs are purely graph-theoretic. They consider the edgeweighted graph described by the matrix as an adjacency matrix and argue about existence of walks of certain weights. We, too, use this graph interpretation of a matrix in two supplementary results (Lemma 2 and Lemma 6). However, the rest of our proof is algebraic. Because our proof is based on the Nachtigall decomposition, which is also applicable to reducible matrices, so is our proof. To the best of our knowledge, we are the first to give transience bounds for reducible matrices. An example by Even and Rajsbaum [3,Fig. 2] shows that our new bounds are asymptotically optimal.

Preliminaries

We consider the max-plus semiring on the set R = R∪{-∞}. That is, we consider the addition (x, y) → max(x, y) and the multiplication (x, y) → x + y. The semiring's zero element is -∞ and its unit is 0. The matrix multiplication of two matrices A and B of compatible size satisfies (AB

) i,j = max k (A i,k + B k,j ).
We call a sequence f : N → R eventually periodic if there exist numbers p, T , and ̺ such that:

(1)

∀n

T : f (n + p) = f (n) + p • ̺
In this case we call p a period, T a transient, and ̺ a ratio of the sequence f . It is easy to see that the ratio is unique and finite if the sequence is not eventually constantly infinite. For every period p, there exists a unique minimal transient T that satisfies [START_REF] Charron-Bost | On the transience of linear max-plus dynamical systems[END_REF]. The next fundamental lemma shows that these minimal transients do, in fact, not depend on p:

Lemma 1. Let f : N → R be eventually periodic. Let p and p be periods of f with respective minimal transients T p and T p . Then T p = T p .

We will henceforth call this unique minimal transient the transient of f . Also, we will call the minimal period the period of f . Cohen et al. [START_REF] Cohen | Analyse du comportement périodique de systèmes de production par la théorie des dioïdes[END_REF] established that the entrywise sequences of matrix powers A n of a square matrix are eventually periodic. More generally, we say that a sequence of matrices is eventually periodic if every entrywise sequence is eventually periodic. Period and transience of a matrix sequence is a period and transience for all entrywise sequences.

The tropical convolution f ⊗ g of two sequences f and g is defined as

(2) (f ⊗ g)(n) = max n 1 +n 2 =n f (n 1 ) + g(n 2 ) .
To a square matrix A naturally corresponds an edge-weighted digraph G(A). The weight p(W ) of a walk W in G(A) is the sum of the weights of its edges. The matrix powers of A satisfy the correspondence (3)

A n i,j = max p(W ) | W has length n and is from i to j .

Nachtigall Decomposition

Nachtigall [START_REF] Nachtigall | Powers of matrices over an extremal algebra with applications to periodic graphs[END_REF] introduced a representation of the sequence of matrix powers of an N × N square matrix as the maximum of at most N matrix sequences whose transients are at most 3N 2 . He showed that this representation can be computed efficiently. However, no results on the transient of the original matrix were obtained. The core of the representation is a decomposition of the original matrix into components corresponding to cycles in the matrix' digraph, The matrix sequences are defined as convolutions corresponding to this decomposition. The following lemma shows the utility of maximum mean cycles for the decomposition. Given an N × N matrix A and a set I ⊆ {1, . . . , N } of indices, we define the deletion of I in A as the matrix B whose entries satisfy B i,j = -∞ if i ∈ I or j ∈ I, and B i,j = A i,j otherwise.

The following lemmas are used to prove the upper bound on the transient of each matrix sequence in the Nachtigall decomposition. Lemma 3. Let f, g : N → R be eventually periodic with common period p, common ratio ̺, and respective transients T f and T g . Then the sequence max(f, g) is eventually periodic with period p, ratio ̺, and transient at most max(T f , T g ).

Lemma 4 ([5, Lemma 6.1]). Let f, g : N → R be eventually periodic with common period p, common ratio ̺, and respective transients T f and T g . Then the convolution f ⊗g is eventually periodic with period p, ratio ̺, and transient at most

T f + T g + p -1.
We now state an improvement of Nachtigall's theorem using essentially the same arguments as the original version. The improvement lies in an upper bound of 2N 2 -N on the sequences' transients instead of 3N 2 .

Theorem 1 (Nachtigall decomposition [5, Theorem 3.3]). Let A be an N × N matrix. Then there exist eventually periodic matrix sequences A 1 (n), A 2 (n), . . . , A N (n) with periods at most N and transients at most 2N 2 -N such that for all n:

(4)

A n = max A 1 (n), A 2 (n), . . . , A N (n)
A common period p of a pair of sequences is the least common multiple of the two periods. Because in the Nachtigall decomposition the periods are at most N , there exists a common period less or equal to N (N -1). Hence S + p can be bounded by 2N 2 .

We thus arrive at the following theorem bounding the transient of the sequence of matrix powers. Denote by A the difference of the maximum and the minimum finite entry in matrix A.

Theorem 2. Let A be an N × N matrix such that G(A) is strongly connected. Denote by λ the maximum cycle mean in G(A) and λ ′ the second largest cycle mean weight. Then the sequence of matrix powers A n has transient at most

2N 2 + A 2N 2 λ -λ ′ .
Hartmann and Arguelles [4, Theorem 10] arrived at a bound of A 2N 2 /(λ -λ 0 ) on the transient, where λ 0 is a parameter of the max-balanced graph of G(A). Their bound is always smaller than ours in Theorem 2. However, in the worst case, both are asympotically in the same order of growth. Also, our technique is different than that of Harmann and Arguelles, and can also be used to provide sharper bounds if information on the Nachtigall decomposition is available.

Our technique is also applicable to the general case where G(A) is not necessarily strongly connected. In the general case, the ratio λ i,j of the sequence of entries (A n ) i,j is equal to the maximum mean of cycles reachable from i and from which j is reachable. Denote by λ ′ i,j the second largest mean of cycles reachable from i and from which j is reachable. By analogous arguments, Theorem 2 continues to hold in the general case if we replace the denominator λ -λ ′ by min i,j (λ i,j -λ ′ i,j ).

Lemma 2 (

 2 [START_REF] Nachtigall | Powers of matrices over an extremal algebra with applications to periodic graphs[END_REF] Lemma 3.2]). If A is an N × N matrix and k is a node of a maximum mean cycle C in G(A), then both sequences A n i,k and A n k,i are eventually periodic with period ℓ(C), ratio p(C)/ℓ(C), and transient at most ℓ(C) • (N -1).

The cyclicity of a strongly connected graph is the greatest common divisor of its cycle lengths.

The proof proceeds by induction on N . The case N = 1 is trivial. If G(A) does not contain a cycle, then (A n ) i,j = -∞ for all n N , so the transient of A is at most N and the theorem's statement is trivially fulfilled when choosing all matrix sequences A m (n) equal to A n .

We hence suppose that G(A) contains a cycle. By the definition of the matrix multiplication, whenever n = n 1 + n 2 , we have:

Let C be a maximum mean cycle in G(A). Denote by B the deletion of the set of C's nodes in A. It follows from the definition of deletion and from the graph interpretation (3) that

In particular, (6) continues to hold when forming the maximum over all n 1 and n 2 such that n = n 1 + n 2 . By writing A i,j (n) = (A n ) i,j and recalling the definition (2) of convolution, we can hence write

Lemmas 2, 3, and 4 imply that the transient of the inner maximum in (7) is at most

and its period is at most ℓ(C) N . Choose the matrix sequence A 1 (n) equal to this inner maximum, i.e., A

By induction hypothesis, there exist matrix sequences A 2 (n),. . . ,A N (n) with periods at most N and transients at most 2N 2 -N such that B n = max A 2 (n), . . . , A N (n) . This then concludes the proof's inductive step.

Transience Bounds

Note that Theorem 1 does not imply that the transient of any sequence of matrix powers is at most 2N 2 -N . The reason for this is that Lemma 3 is not applicable to the maximum in the Nachtigall decomposition because the involved sequences can have different ratios.

The following lemma is our main technical novelty and provides a tool for bounding the transient of a maximum of two eventually periodic sequences if their ratios are not equal.

Lemma 5. Let f, g : N → R be eventually periodic with the same period p, respective ratios ̺ f and ̺ g , and respective transients T f and T g .

Assume that ̺ f ̺ g and that for all n S we have g(n) = -∞ whenever f (n) = -∞. Then the sequence max(f, g) is eventually periodic with period p, ratio max(̺ f , ̺ g ), and transient at most

In the rest of this section, we provide general transience bounds for sequences of matrix powers. We do this by applying Lemma 5 entrywise to the maximum in [START_REF] Hartmann | Transience bounds for long walks[END_REF]. Evidently, given a Nachtigall decomposition (which is not unique), one can use Lemma 5 to bound the transient of the matrix powers. In this section, we proceed to use the existence of a Nachtigall decomposition to prove general transience bounds independent of an explicit decomposition.

We first assume that the graph G(A) is strongly connected. In this case, all sequences (A n ) i,j are eventually periodic with ratio equal to the maximum cycle mean in G(A). For every pair (i, j) of indices, the ratio of the sequence A m (n) i,j is greater or equal to that of A m+1 (n) i,j . We want to apply Lemma 5 to every pair of (i) a sequence of maximum ratio and (ii) a sequence of another ratio. Afterwards, we apply Lemma 3 to the resulting maxima (which all have the same ratio). But to effectively apply Lemma 5, we have to bound its parameter S for every pair.

We show that the parameter S is at most N (N + 1) with a graphtheoretic argument: The exploration penalty of graph G is the least integer ep such that there exists a closed walk of length n at every node in G for all multiples n of G's cyclicity 1 that satisfy n ep.

Lemma 6 ([1, Theorem 3]). The exploration penalty of a graph with N nodes is at most N (N -1).

It is well-known that the difference of lengths of two walks from i to j in a strongly connected graph is always a multiple of the graph's cyclicity. In each step of the Nachtigall recursion, there exists a path from i to j via a node k of C of length at most 2N . Hence Lemma 6 implies that if there exists any path from i to j of length n 2N + N (N -1) = N (N + 1), then there exists also a path from i to j via k of length n. This shows that S can be chosen to be at most N (N + 1).