Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-sonnet-4-20250514· AnthropicHugging Face LMArena Human Preference 140K

can any directed acyclic graph be represented as a strictly upper triangular matrix?

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Metallama-4-maverick-03-26-experimental’s answer.
  1. User

    can any directed acyclic graph be represented as a strictly upper triangular matrix?

  2. Claude Assistant

    Yes, any directed acyclic graph (DAG) can be represented as a strictly upper triangular matrix through its adjacency matrix, but this requires ordering the vertices appropriately.

    The key insight is that a DAG can always be topologically sorted - that is, the vertices can be ordered such that for every directed edge (u,v), vertex u appears before vertex v in the ordering. This is possible precisely because the graph has no cycles.

    Once you have a topological ordering of the vertices, you can construct the adjacency matrix by:

    1. Labeling the vertices 1, 2, ..., n according to the topological order
    2. Creating an n×n matrix where entry (i,j) = 1 if there's an edge from vertex i to vertex j, and 0 otherwise

    Because of the topological ordering, all edges go from lower-numbered vertices to higher-numbered vertices, which means all the 1's in the adjacency matrix appear above the main diagonal. The matrix is strictly upper triangular (all entries on and below the main diagonal are 0).

    Conversely, any strictly upper triangular adjacency matrix represents a DAG, since the natural vertex ordering (1, 2, ..., n) is already a valid topological ordering.

    This relationship is fundamental in graph theory and has practical applications in algorithms for DAG processing, where working with the upper triangular representation can simplify certain computations.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.