Verify Eigenvector

A vector v is an eigenvector of A with eigenvalue λ exactly when multiplying A by v is the same as multiplying v by the scalar λ. In code, you just need to check whether $A\mathbf{v}$ equals $\lambda \mathbf{v}$ (up to any tolerance if using floats).

---

1. Background Knowledge

• An eigenvector of a matrix $A$ is a nonzero vector $\mathbf{v}$ such that applying the linear transformation $A$ to $\mathbf{v}$ only scales it, not change its direction:

$$A\mathbf{v} = \lambda \mathbf{v}.$$

Here, $\lambda$ is the corresponding eigenvalue.

• If you write $A$ as an $m \times n$ matrix and $\mathbf{v}$ as an $n \times 1$ vector, then $A\mathbf{v}$ is just standard matrix–vector multiplication. The equation $A$\mathbf{v}$=$\lambda$\mathbf{v}$ is a vector equality: all components must match.

• In this problem, you are not asked to find eigenvalues or eigenvectors; you are given $A$, $\mathbf{v}$, and $\lambda$, and you only need to verify whether the eigenvector relationship holds.

---

2. Algorithm / Approach

Conceptual approach:

1. Compute the matrix–vector product $u = A\mathbf{v}$.
2. Compute the scaled vector $w =$\lambda$\mathbf{v}$.
3. Compare $u$ and $w$ entry by entry:

• If they are equal (or within a small tolerance for floating-point), then v is an eigenvector with eigenvalue λ.
• Otherwise, it is not.

If the problem uses integers and exact equality, you can use a simple equality check. If it uses floats, use a small tolerance (e.g., check that the absolute difference of each component is less than some epsilon).

---

3. Step-by-Step Strategy

1. Read inputs

• Matrix $A$ of size $n \times n$ (or possibly $m \times n$).
• Vector $\mathbf{v}$ of size $n$.
• Scalar $\lambda$.

2. Compute $A\mathbf{v}$ For each row $i$ of $A$:

$$u_i = \sum_{j=1}^{n} A_{ij} \cdot v_j$$

Store results in array u.

3. Compute $\lambda \mathbf{v}$ For each index $i$:

$$w_i = \lambda \cdot v_i$$

Store results in array w.

4. Compare vectors

• For each index $i$, check if u[i] equals w[i].
• If using floats, check abs(u[i] - w[i]) <= eps for some small eps, e.g. 1e-6.

5. Return / print result

• If all components match, output something like "True" / 1 / "YES" depending on the platform.
• Otherwise, output "False" / 0 / "NO".

Example skeleton (Python-like pseudocode):

def is_eigenvector(A, v, lam, eps=1e-9):
 n = len(v)
 # compute A v
 u = [0.0] * n
 for i in range(n):
 for j in range(n):
 u[i] += A[i][j] * v[j]
 # compute λ v
 w = [lam * v[i] for i in range(n)]
 # compare
 for i in range(n):
 if abs(u[i] - w[i]) > eps:
 return False
 return True

---

4. Common Pitfalls

• Forgetting nonzero condition: By definition, an eigenvector must be nonzero. Some problems implicitly assume the given vector is nonzero; check the statement. If not, you may need to treat the zero vector as “not an eigenvector.”

• Dimension mismatch: Ensure the length of $\mathbf{v}$ matches the number of columns of $A$. Otherwise, $A\mathbf{v}$ is not defined.

• Floating-point precision:

• Using exact equality (==) with floats can fail due to rounding.

• Prefer comparing with a small tolerance eps.

• Confusing direction vs. value: $A\mathbf{v}$ must equal $\lambda\mathbf{v}$ component-wise. It is not enough that they just “look proportional” unless you explicitly compute $\lambda \mathbf{v}$ and compare.

---

5. Time & Space Complexity

• Time complexity

• Computing $A\mathbf{v}$ takes $O(n^2)$ for an $n \times n$ matrix.

• Computing $\lambda \mathbf{v}$ takes $O(n)$.

• Comparing vectors takes $O(n)$.

• Overall: $O(n^2)$.

• Space complexity

• You need space for vectors $u$ and $w$, each of size $n$.

• Overall auxiliary space: $O(n)$ (besides the input storage).