The Central Idea
A table or array organizes information according to positions.
Instead of storing isolated values, we identify where each value belongs:
\[ \boxed{\text{entry}=\text{row position}+\text{column position}}. \]This positional structure makes discrete information easier to encode and analyze.
Incidence structures add a further idea: a table entry can indicate whether two objects participate in a specified relationship.
What Is a Table?
A table organizes information into rows and columns.
For example:
| Item | Category | Quantity |
|---|---|---|
| A | Red | 4 |
| B | Blue | 7 |
| C | Red | 2 |
Each row may represent an object, while each column may represent an attribute of that object.
Rows
A row is a horizontal collection of entries.
In a data table, one row commonly represents one record or observation.
For example,
\[ (\text{A},\text{Red},4) \]can be viewed as one ordered record stored across a row.
Columns
A column is a vertical collection of entries.
Columns commonly represent attributes, variables, categories, or indexed positions.
If a quantity column contains
\[ 4,\ 7,\ 2, \]then these values share the same structural role even though they belong to different rows.
What Is an Array?
An array is an indexed arrangement of entries.
A one-dimensional array may look like
\[ [5,8,2,9]. \]A two-dimensional array may be displayed as
\[ \begin{bmatrix} 1&4&7\\ 2&5&8 \end{bmatrix}. \]Arrays generalize the ordered structures from earlier lessons by allowing entries to be indexed along more than one dimension.
One-Dimensional Arrays
A one-dimensional array resembles a finite list.
For example,
\[ A=[10,20,30,40]. \]Under zero-based indexing,
\[ A_0=10,\quad A_1=20,\quad A_2=30,\quad A_3=40. \]The index identifies position.
Two-Dimensional Arrays
A two-dimensional array uses two indices.
We may write
\[ A_{ij} \]for the entry in row \(i\) and column \(j\).
For
\[ A= \begin{bmatrix} 3&5\\ 7&9 \end{bmatrix}, \]we have
\[ A_{11}=3,\qquad A_{12}=5,\qquad A_{21}=7,\qquad A_{22}=9. \]Shape of an Array
A rectangular array with \(m\) rows and \(n\) columns has shape
\[ m\times n. \]For example,
\[ \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix} \]has shape
\[ \boxed{2\times3}. \]The first number counts rows; the second counts columns.
Number of Entries
An \(m\times n\) array contains
\[ \boxed{mn} \]positions.
Thus a \(4\times7\) array contains
\[ 4\cdot7=28 \]entries.
Matrices as Arrays
A matrix is a rectangular array whose entries are treated mathematically.
For example,
\[ M= \begin{bmatrix} 1&0&1\\ 0&1&1 \end{bmatrix}. \]In this lesson, matrices are mainly used as discrete data structures and relationship encodings.
Matrix algebra is developed elsewhere in Malone Math.
Tables versus Matrices
A table may contain mixed kinds of data:
- names;
- categories;
- dates;
- counts;
- labels.
A matrix usually emphasizes entries that participate in a unified mathematical structure.
The physical row-column layout may be similar even when the interpretation differs.
Headers Are Metadata
Row and column labels are often not themselves data entries.
They provide metadata describing what the positions mean.
For example, in a table with columns
\[ \text{Name},\quad\text{Age},\quad\text{Score}, \]these labels describe the roles of the values stored beneath them.
Rows as Tuples
A row of a table can often be viewed as a tuple.
For example,
\[ (\text{Ada},19,88) \]may represent one person's name, age, and score.
The order of the fields matters because each position has a different interpretation.
Columns as Variables
A column often records the values of one variable across many objects.
For example:
| Object | Weight |
|---|---|
| A | 12 |
| B | 9 |
| C | 15 |
The weight column collects measurements sharing the same meaning.
Binary Tables
A binary table uses entries such as
\[ 0 \]and
\[ 1 \]to represent two possibilities.
A common convention is:
\[ 1=\text{present or true}, \] \[ 0=\text{absent or false}. \]Binary Membership Encoding
Suppose
\[ A=\{a,b,c,d\}. \]The subset
\[ \{a,c\} \]can be encoded as
\[ [1,0,1,0]. \]Each position records whether the corresponding element belongs to the selected subset.
What Is Incidence?
Incidence records whether one type of object participates in, belongs to, touches, or is associated with another type of object.
Examples include:
- a vertex incident to an edge;
- a student enrolled in a course;
- a person belonging to a committee;
- a point lying on a line;
- a product supplied by a vendor.
Incidence Structures
An incidence structure consists of objects together with a rule specifying which objects are incident.
One common model uses two sets,
\[ P \]and
\[ B, \]together with an incidence relation
\[ I\subseteq P\times B. \]The two sets may represent points and blocks, vertices and edges, or any other paired object types.
Incidence Tables
An incidence relation can be displayed as a binary table.
Suppose students may enroll in courses:
| Course A | Course B | Course C | |
|---|---|---|---|
| Student 1 | 1 | 0 | 1 |
| Student 2 | 0 | 1 | 1 |
A \(1\) records enrollment; a \(0\) records non-enrollment.
Incidence Matrices
When the entries of an incidence table are placed into a matrix, the result is an incidence matrix.
For the previous example,
\[ M= \begin{bmatrix} 1&0&1\\ 0&1&1 \end{bmatrix}. \]Rows correspond to one object type, columns to another, and entries encode the relation.
Graph Incidence Matrices
A graph can be represented by listing vertices as rows and edges as columns.
An entry indicates whether a vertex is incident to an edge.
Suppose
\[ e_1=\{A,B\} \]and
\[ e_2=\{B,C\}. \]Then one incidence matrix is
\[ \begin{bmatrix} 1&0\\ 1&1\\ 0&1 \end{bmatrix}. \]Reading a Graph Incidence Matrix
In
\[ \begin{bmatrix} 1&0\\ 1&1\\ 0&1 \end{bmatrix}, \]the first column indicates that edge \(e_1\) touches vertices \(A\) and \(B\).
The second column indicates that \(e_2\) touches vertices \(B\) and \(C\).
Thus the matrix encodes the same graph information as an edge list.
Adjacency Tables
A graph relation can also be represented by placing the same vertex set on both rows and columns.
An entry records whether the row vertex is adjacent to the column vertex.
This produces the adjacency matrix introduced in the previous lesson.
Example: Adjacency Matrix
Suppose
\[ V=\{A,B,C\} \]with edges
\[ \{A,B\},\qquad\{B,C\}. \]The adjacency matrix is
\[ \boxed{ \begin{bmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{bmatrix} }. \]Why the Diagonal Is Zero Here
In the previous simple graph, no vertex has a loop.
Therefore,
\[ A_{11}=A_{22}=A_{33}=0. \]A \(1\) on the diagonal would indicate that a vertex is adjacent to itself through a loop in a model where loops are allowed.
Symmetry in Undirected Adjacency Tables
In an undirected graph,
\[ A\text{ adjacent to }B \]is equivalent to
\[ B\text{ adjacent to }A. \]Therefore the adjacency matrix is symmetric:
\[ M_{ij}=M_{ji}. \]Directed Adjacency Tables
A directed graph need not produce a symmetric adjacency matrix.
If
\[ A\to B \]exists but
\[ B\to A \]does not, then
\[ M_{AB}=1 \]while
\[ M_{BA}=0. \]Relation Matrices
More generally, any finite relation
\[ R\subseteq A\times B \]can be encoded by a binary matrix.
Define
\[ M_{ij}= \begin{cases} 1,&(a_i,b_j)\in R,\\ 0,&(a_i,b_j)\notin R. \end{cases} \]This converts a relation into a positional data structure.
Rows as Source Objects
In a relation matrix, each row corresponds to one source object.
The pattern of \(1\)'s in that row identifies all target objects related to it.
A row containing
\[ [0,1,1,0] \]indicates incidence with the second and third column objects.
Columns as Target Objects
Each column records which source objects are related to one target object.
A column such as
\[ \begin{bmatrix} 1\\ 0\\ 1 \end{bmatrix} \]indicates that the first and third source objects are incident to that target.
Row Sums
In a binary incidence table, the sum of a row counts how many incidences are recorded for the corresponding row object.
For example,
\[ [1,0,1,1,0] \]has row sum
\[ \boxed{3}. \]The row object participates in three recorded relationships.
Column Sums
A column sum counts how many row objects are incident to the corresponding column object.
Thus row and column sums provide simple structural summaries of a binary table.
In graph incidence matrices, these sums can encode vertex degrees or edge endpoint counts depending on orientation.
Frequency Tables
A frequency table records how many observations fall into each category.
For example:
| Category | Frequency |
|---|---|
| A | 5 |
| B | 8 |
| C | 3 |
Frequency tables compress repeated observations into counts.
Total Frequency
The total number of observations in a frequency table is the sum of its frequencies.
If the frequencies are
\[ 5,\ 8,\ 3, \]then the total is
\[ \boxed{5+8+3=16}. \]Contingency Tables
A contingency table organizes counts according to two categorical variables.
For example:
| Option A | Option B | |
|---|---|---|
| Group 1 | 12 | 8 |
| Group 2 | 7 | 13 |
Each cell records the count belonging simultaneously to one row category and one column category.
Marginal Totals
Row totals and column totals in a contingency table are called marginal totals.
They summarize one category while ignoring the subdivision created by the other category.
These tables will appear again in probability and statistics.
Truth Tables
A truth table is another important finite table.
It lists possible truth-value assignments and the resulting value of a logical expression.
For conjunction:
| \(P\) | \(Q\) | \(P\land Q\) |
|---|---|---|
| True | True | True |
| True | False | False |
| False | True | False |
| False | False | False |
State Tables
A finite-state system may be represented by a state-transition table.
For example:
| Current state | Input 0 | Input 1 |
|---|---|---|
| A | A | B |
| B | C | A |
| C | B | C |
The table encodes the same transition information that could be drawn as a directed state graph.
Lookup Tables
A lookup table stores outputs for known inputs.
For a finite function,
\[ f:A\to B, \]a lookup table may list every
\[ x \]together with
\[ f(x). \]This can be more practical than giving a formula.
Arrays as Functions on Index Sets
An array can be interpreted as a function from index positions to values.
A two-dimensional array of shape \(m\times n\) may be viewed as
\[ A:\{1,\ldots,m\}\times\{1,\ldots,n\}\to S. \]The ordered pair
\[ (i,j) \]identifies a position, and \(A(i,j)\) gives the value stored there.
Sparse Structures
A table or matrix is sparse when most possible entries are empty, zero, or absent.
Many large graphs are sparse because each vertex is connected to only a small fraction of all possible vertices.
Sparse structures often benefit from compact representations such as adjacency lists rather than full matrices.
Dense Structures
A structure is dense when many possible relationships are present.
For dense finite relations, matrix representations may be especially convenient because many entries contain meaningful values.
Representation choice often depends on structural density.
Data Types in Tables
A table may contain several kinds of data.
Entries may be:
- numbers;
- categories;
- Boolean values;
- strings;
- symbols;
- sets;
- other discrete objects.
The interpretation of each column determines what operations make sense.
Missing Data
A blank table entry may mean several different things:
- the value is unknown;
- the value is not applicable;
- the value was not measured;
- the relationship is absent.
These meanings should not be silently treated as equivalent.
Zero Is Not Always the Same as Missing
A numerical entry of
\[ 0 \]is a known value.
A missing entry means the value is unavailable or undefined according to the model.
Confusing these two cases can change counts, averages, relationships, and algorithmic behavior.
Rectangular Data
Many datasets are called rectangular because every row follows the same column structure.
If every record has fields
\[ (\text{ID},\text{category},\text{value}), \]then all rows can be aligned under those three columns.
This regularity supports systematic processing.
Arrays beyond Two Dimensions
Arrays can have more than two indices.
A three-dimensional array might use entries
\[ A_{ijk}. \]One index could represent location, another time, and another category.
Higher-dimensional arrays are useful when several discrete coordinates are needed simultaneously.
Tables as Encodings
A table is not merely a display.
It can serve as an exact encoding of a discrete structure.
A relation, graph, mapping, state machine, or collection of observations can often be reconstructed completely from an appropriate table.
Different Representations of the Same Structure
The same relation might be written as ordered pairs,
\[ \{(a,1),(b,1),(b,2)\}, \]drawn as arrows, or encoded by the matrix
\[ \begin{bmatrix} 1&0\\ 1&1 \end{bmatrix}. \]These representations differ in form but preserve the same underlying incidence information.
Why Representation Matters
Different representations make different tasks easier.
A table may make individual values easy to inspect.
A matrix may support algebraic operations.
A graph drawing may make connectivity visually obvious.
An adjacency list may save space in a sparse network.
Choosing a representation is part of solving the problem.
Common Error: Reversing Rows and Columns
In
\[ A_{ij}, \]the first index conventionally identifies the row and the second identifies the column.
Thus
\[ A_{23} \]means row \(2\), column \(3\), not row \(3\), column \(2\).
Common Error: Confusing Shape with Number of Entries
A \(3\times4\) array has shape
\[ 3\times4 \]but contains
\[ 3\cdot4=12 \]entries.
Shape and total size describe different properties.
Common Error: Treating Headers as Data
The word
\[ \text{Quantity} \]at the top of a column describes the entries below it.
It is usually metadata rather than one of the observations being analyzed.
Common Error: Assuming Zero Means Missing
In a binary incidence matrix,
\[ 0 \]usually explicitly means that the relationship is absent.
A blank or unknown value may mean something entirely different.
Common Error: Assuming Every Matrix Is an Adjacency Matrix
A rectangular matrix may represent many structures.
It could be:
- a data array;
- a relation matrix;
- an incidence matrix;
- a transition matrix;
- a numerical transformation.
Interpretation depends on the row labels, column labels, and modeling rules.
Common Error: Ignoring Orientation
In an incidence table, swapping the row and column object types changes how the table is interpreted.
A student-by-course table and a course-by-student table may contain transposed information, but the role of each axis has changed.
A Reliable Procedure for Reading a Table or Array
- Identify what each row represents.
- Identify what each column represents.
- Determine the indexing convention.
- Determine the shape of the array.
- Interpret the meaning of each entry.
- Distinguish labels and metadata from stored values.
- Identify whether entries are numerical, categorical, Boolean, or symbolic.
- Determine whether zeros, blanks, and missing values have different meanings.
- Check whether row or column sums carry structural meaning.
- Relate the table to any underlying set, relation, graph, or state model.
Example: Reading an Incidence Matrix
Suppose
\[ M= \begin{bmatrix} 1&0&1\\ 0&1&1\\ 1&0&0 \end{bmatrix}. \]Let rows represent people
\[ P_1,P_2,P_3 \]and columns represent projects
\[ Q_1,Q_2,Q_3. \]Then \(P_1\) participates in \(Q_1\) and \(Q_3\), \(P_2\) participates in \(Q_2\) and \(Q_3\), and \(P_3\) participates only in \(Q_1\).
Practice 1: Array Shape
Find the shape of
\[ \begin{bmatrix} 1&2&3\\ 4&5&6\\ 7&8&9\\ 10&11&12 \end{bmatrix}. \]Practice 2: Number of Entries
How many entries are contained in a
\[ 6\times8 \]array?
Practice 3: Indexed Entry
Let
\[ A= \begin{bmatrix} 4&7&9\\ 2&5&8 \end{bmatrix}. \]Find \(A_{23}\).
Practice 4: Binary Membership
Let
\[ S=\{a,b,c,d,e\}. \]Which subset is represented by
\[ [1,0,1,1,0]? \]Practice 5: Row Sum
Find the sum of the binary row
\[ [1,1,0,1,0,1]. \]Practice 6: Frequency Total
A frequency table has counts
\[ 7,\quad12,\quad5,\quad6. \]Find the total number of observations.
Practice 7: Graph Incidence
Suppose edge
\[ e=\{A,C\}. \]Which vertices should receive a \(1\) in the incidence-matrix column for \(e\)?
Practice 8: Undirected Symmetry
In an undirected adjacency matrix, if
\[ M_{24}=1, \]what must \(M_{42}\) equal?
Practice 9: Missing versus Zero
Explain why a blank table entry should not automatically be replaced by
\[ 0. \]Practice 10: Representation Choice
A network has one million vertices, but each vertex is connected to only a few others.
Would a full adjacency matrix or a compact adjacency-list representation generally be more space-efficient?
Practice Answers
Practice 1
The array has four rows and three columns:
\[ \boxed{4\times3}. \]Practice 2
\[ 6\cdot8=\boxed{48}. \]Practice 3
Row \(2\), column \(3\) contains
\[ \boxed{8}. \]Practice 4
The first, third, and fourth elements are included:
\[ \boxed{\{a,c,d\}}. \]Practice 5
\[ 1+1+0+1+0+1=\boxed{4}. \]Practice 6
\[ 7+12+5+6=\boxed{30}. \]Practice 7
The column should contain \(1\)'s in the rows for
\[ \boxed{A\text{ and }C}. \]Practice 8
An undirected adjacency matrix is symmetric:
\[ \boxed{M_{42}=1}. \]Practice 9
A blank may mean unknown, unavailable, or not applicable. A numerical zero is a known value. Replacing missing information with zero changes the meaning of the data.
Practice 10
The graph is sparse, so an adjacency list generally stores only the connections that actually exist and is therefore more space-efficient than a full million-by-million adjacency matrix.
What to Remember
- Tables organize discrete information into rows and columns.
- Arrays store entries at indexed positions.
- An \(m\times n\) array contains \(mn\) entries.
- A matrix is a mathematically structured rectangular array.
- Incidence records whether two objects participate in a specified relation.
- Binary matrices can encode membership, relations, graphs, and state structure.
- Adjacency matrices encode vertex-to-vertex connections.
- Incidence matrices often encode object-to-relationship connections.
- Row and column sums can summarize structural counts.
- Representation choice affects clarity, storage, and computation.
The central habit is: before reading the entries, identify exactly what the rows, columns, and values represent.
Where We Go Next
Tables and arrays organize discrete information at fixed positions. The next step is to examine quantities that change only at separated inputs or in stepwise jumps rather than continuously.
The next lesson, Discrete Functions and Stepwise Change, develops functions defined on discrete domains, sequences of values, jumps, finite differences, and stepwise models.