Orbit of a matrix can generates a basis?

A matrix (associated to an endomorphism) for which it exists $v$ such that $(v,Av, \dots, A^{n-1})$ is linearly independent is called a cyclic endomorphism. This is a direct French translation and I'm not sure that this is a proper English mathematical wording.

At least Wikipedia mentions that a vector $v$ for which $(v,Av, \dots, A^{n-1})$ spans $V$ is a cyclic vector.

You can have a look to French Wikipedia Decomposition de Frobenius, in particular the paragraph Endomorphisme cyclique. Unfortunately, the English version seems to lack a similar paragraph.

This paragraph mentions equivalent conditions for an endomorphism $u$ to be cyclic:

• the degree of the minimum polynomial of $u$ is equal to the dimension of $V$,

• the minimal polynomial and the characteristic polynomial of $u$ are equal (with the sign near);

• an endomorphism commutes with $u$ (if and) only if it is a polynomial in $u$;

• there is a base of $V$ in which the matrix of $u$ is a companion matrix. It is then the companion matrix of the minimal polynomial of $u$.

This is basically a restatement of the problem, but it still might be useful.

For every vector $v \in V$ there exists a unique monic polynomial $p$ of minimal degree such that $p(A)v = 0$.

Namely, the minimal polynomial $m_A$ of $A$ annihilates $A$ so the set of all monic polynomials $q$ such that $q(A)v = 0$ is nonempty. Consider the polynomials of minimal degree.

Let $p,q$ be two such polynomials. Then $(q-r)(A)v = q(A)v - r(A)v = 0$ and $q-r$ is of lesser degree than the minimal, which implies $q = r$.

As a consequence, if $q(A)v= 0$ then $p \,|\,q$. Namely, $\deg q \ge \deg p$ so there exist unique $g, h$ such that $p = qg + h$ with $\deg h < \deg p$. In particular

$$0 = q(A)v = g(A)p(A)v + h(A)v = h(A)v \implies h = 0 \implies p \,|\,q$$

Note that $\deg p \le n$ because $\deg m_A \le n$ and $p \,|\, m_A$.

Therefore, linear independence of $\{v, Av, \ldots, A^{n-1}v\}$ is equivalent to the fact that $\deg p = n$, which in turn is equivalent to $m_A = p$.

The answer to your question "when $(*)$ the orbit $\{v,Av,\cdots,A^{n-1}v\}$ over a vector space $V$ can generate a basis of $V$ ?" is, in a probabilistic point of view: ALWAYS.

Indeed, let $\chi_A$ be the characteristic polynomial of $A$ and $discr_A$ be its discriminant. The set $Z$ of $A\in M_n(\mathbb{C})$ s.t. $discr_A\not= 0$ is Zariski open dense. Thus, if the entries of $A$ are randomly chosen (using a normal law for example) then $A\in Z$ (that is $A$ has $n$ distinct eigenvalues) with probability $1$. We may assume that $A$ is diagonal; then the vector $v=[1,\cdots,1]^T$ realizes $(*)$ and more generally, a randomly chosen vector realizes $(*)$ with probability $1$; therefore, when $A\in Z$ (not in a diagonal form) then a random vector realizes $(*)$ with probability $1$.

Of course, there exist matrices, with multiple eigenvalues, that have the considered property. cf. the other answers.