Linear Algebra for MLMedium
Average Consensus on a Communication Graph
~20 mincode completion
Implement average_consensus(A, x0, eps, T):
- build L=D−A from the adjacency matrix,
- apply exactly T times, computing every agent from the same previous state (no in-place, one-agent-at-a-time updates),
- return the final states as a list of floats.
Do not clip or stop early. If is past the stability limit the states should grow, and one test checks that they do.
Examples
Worked example: one step on a 3-agent path
- Input
- average_consensus([[0, 1, 0], [1, 0, 1], [0, 1, 0]], [6, 0, 3], 0.25, 1)
- Output
- [4.5, 2.25, 2.25]
Path of 4 agents drifts toward the average 2.0
- Input
- average_consensus([[0, 1, 0, 0], [1, 0, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]], [10, 0, 0, -2], 0.3, 25)
- Output
- [2.040836, 2.016915, 1.983085, 1.959164]
Complete graph of 4 agents: every mode shrinks by 0.2 per step
- Input
- average_consensus([[0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 0]], [1, 2, 3, 10], 0.2, 5)
- Output
- [3.99904, 3.99936, 3.99968, 4.00192]
Hints
Hint 1
Use a matrix product rather than nested loops, and check which operand transposes.
Hint 2
Watch for this: laplacian sign flipped as a minus d.
Requirements
A: Symmetric 0/1 adjacency matrix, shape (n, n)x0: Initial states, shape (n,)eps: Step size: Number of steps
Return Final states as a list of n floats.
Constraints
Allowed library: NumPy only
Time limit: 200 ms, Memory: 64 MB
Where this shows up
~20 min
••••••••••
5 employers weight this skill
4 quant funds, 1 defense company. Top match scores 92.
Python
import numpy as np
def average_consensus(A, x0, eps: float, T: int) -> list:
"""
Run T steps of average consensus x <- x - eps * L x.
Args:
A: Symmetric 0/1 adjacency matrix, shape (n, n)
x0: Initial states, shape (n,)
eps: Step size
T: Number of steps
Returns:
Final states as a list of n floats.
"""
A = np.asarray(A, dtype=float)
x = np.asarray(x0, dtype=float).copy()
# YOUR CODE HERE
pass