Gaia Early Data Release 3. Building the Gaia DR3 source list -- Cross-match of Gaia observations

The Gaia Early Data Release 3 (Gaia EDR3) contains results derived from 78 billion individual field-of-view transits of 2.5 billion sources collected by the European Space Agency's Gaia mission during its first 34 months of continuous scanning of the sky. We describe the input data, which have the form of onboard detections, and the modeling and processing that is involved in cross-matching these detections to sources. For the cross-match, we formed clusters of detections that were all linked to the same physical light source on the sky. As a first step, onboard detections that were deemed spurious were discarded. The remaining detections were then preliminarily associated with one or more sources in the existing source list in an observation-to-source match. All candidate matches that directly or indirectly were associated with the same source form a match candidate group. The detections from the same group were then subject to a cluster analysis. Each cluster was assigned a source identifier that normally was the same as the identifiers from Gaia DR2. Because the number of individual detections is very high, we also describe the efficient organising of the processing. We present results and statistics for the final cross-match with particular emphasis on the more complicated cases that are relevant for the users of the Gaia catalogue. We describe the improvements over the earlier Gaia data releases, in particular for stars of high proper motion, for the brightest sources, for variable sources, and for close source pairs.