Yes, you're right. The only way I can think of to handle it (in Scala, I suppose you can't do it in Rust) would be via implicit parameters. You would basically have a Times trait, and a TimesOp trait.

    trait TimesOp[L,R,O] {
        def times(L left, R right): O
    }

    object TimesOps {
        implicit object ScalarMatrixTimesOp[S] extends TimesOp[S,Matrix[S],Matrix[S]] {
            override def times(S left, Matrix[S] right): Matrix[S] = {
                ...
            }
        }
    }

    trait Times { self: L =>
        def *[R,O](R right, implicit timesOp: TimesOp[L,R,O]): O =
            timesOp.times(this, right)
    }

I'm sure I got something wrong here, but I think the basic idea works. In any case, it goes to show that getting this behavior in a language with strongly-typed generics is non-trivial.