%%% Document Class

\documentclass[11pt]{letter}
\usepackage[margin=1in]{geometry}


%%% Packages

\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{hyperref}


%%% Variables

\newcommand{\courseName}{Math 480A2}
\newcommand{\hwNumber}{13}
\newcommand{\hwDueDate}{December 1, 2022}


%%% Definitions

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\iff}{\leftrightarrow}

\renewcommand{\vec}[1]{\mathbf{#1}}

\DeclareMathOperator{\Prob}{Pr}               % probability
\newcommand{\Exp}{\mathbb{E}}                 % expected value
\newcommand{\C}{{\rm c}}                      % complement
\newcommand{\card}[1]{\left|#1\right|}        % cardinality
\newcommand{\Pv}{\mathcal{P}}                 % prover
\newcommand{\Vf}{\mathcal{V}}                 % verifier

\DeclareMathOperator{\AND}{AND}
\DeclareMathOperator{\OR}{OR}

\renewcommand{\theenumi}{\Alph{enumi}}
\newcounter{saveenum}

%%% Document

\begin{document}

\begin{center}
	{\large \courseName, Homework \hwNumber}\\
	Due \hwDueDate\\
\end{center}

{\small \textit{Homework is graded out of a total of 10 points.  Collaboration is permitted, but you must list all coauthors on a problem's solution at the top of the page, and your writing must be your own.}}

\vspace{5mm}

\textbf{Problem 1.} (5 points) Let $F$ be a finite field, and let $M$ be an $n \times n$ matrix with entries in $F$.  Recall that an \textit{eigenvector} of $M$ is a nonzero vector $\vec{v}$ such that $M \vec{v} = \alpha \vec{v}$ for some $\alpha \in F$.  Give an R1CS instance which, in conjunction with the polynomial IOP for R1CS-Sat we learned about in lecture, allows a prover to convince a verifier that they know an eigenvector of $M$.  (\textit{Hint.} A vector $\vec{v}$ is nonzero if and only if there exists a vector $\vec{w}$ whose dot product with $\vec{v}$ is equal to 1.)

\vspace{3mm}

\textbf{Problem 2.} (5 points) Review the steps of the polynomial IOP for R1CS-Satisfiability we discussed in class, and make a list of all of the polynomial commitments sent from the prover to the verifier in the protocol, the degree bounds for the committed polynomials, and the number of times each commitment is opened.  For this list, you may interpret the bivariate polynomials $\hat{M}$ as polynomial commitments of ``degree'' less than $n^2$.  Do the number of commitments and the number of openings depend on the size of the input R1CS instance?

\end{document}